Języki, automaty i obliczenia/Wykład 2: Gramatyka jako model obliczen. Hierarchia Chomsky'ego

From Studia Informatyczne

W tym wykładzie wprowadzimy ogólne pojęcie systemu przepisującego, zdefiniujemy gramatykę, czyli szczególny typ systemu przepisującego oraz określimy cztery typy gramatyk wprowadzone przez Noama Chomsky'ego.

Kurt Goedel (1906-1978)Zobacz biografię
Enlarge
Kurt Goedel (1906-1978)
Zobacz biografię
Teoria języków formalnych i automatów tworzy i bada pewne modele obliczeń, można popularnie powiedzieć modele komputera, zwane automatami lub gramatykami. Jednym z głównych i ogólnych problemów wokół którego skupione są badania tej teorii jest problem możliwości i ograniczeń obliczeniowych. Początki tych rozważań sięgają lat trzydziestych ubiegłego stulecia i wiążą się z pracami K.Goedla i późniejszymi A.Turinga i A.Churcha. Równolegle do teorii automatów problematyka ta jest intensywnie badana w ramach teorii obliczalności i teorii złożoności.

W tym wykładzie wprowadzimy pierwszy z tych modeli, mianowicie gramatykę. Określimy także sposób wyprowadzenia (generowania) słowa zgodnie z regułami gramatycznymi i zdefiniujemy język opisywany przez gramatykę. Przedstawimy również podstawowe typy gramatyk wprowadzone do lingwistyki teoretycznej i później do teorii języków formalnych przez Noama Chomsky'ego, twórcę pojęcia gramatyki transformacyjno-generatywnej, co miało miejsce w roku 1957.

Alonso Church (1903-1995)Zobacz biografię
Enlarge
Alonso Church (1903-1995)
Zobacz biografię
Przez gramatykę rozumie się systematyczny opis wybranego języka naturalnego, opis, który obejmuje jego składnię (syntaktykę), znaczenie (semantykę) i fonologię, czyli dźwiękowy system języka. Reguły składni określają regularności rządzące kombinacjami słów, semantyka bada znaczenie słów i zdań, a fonologia wyróżnia dźwięki i ich dopuszczalne zestawienia w opisywanym języku.

Teoria języków formalnych bada wyłącznie syntaktyczne własności języków. Język rozumiany jest abstrakcyjnie, jako zbiór skończonych napisów. Zatem opierając się na wiadomościach z poprzedniego wykładu możemy powiedzieć, że język (formalny) L to dowolny podzbiór wolnego monoidu A^{*}. Baza tego wolnego monoidu, czyli zbiór {A} to alfabet, a sam wolny monoid możemy interpretować, jako zbiór wszystkich możliwych napisów utworzonych w tym alfabecie. Na ogół język L jest właściwym podzbiorem A^{*}, czyli składa się z pewnych tylko ("poprawnych") napisów. Wyróżniając język L zazwyczaj wprowadzamy pewne kryteria, które muszą spełniać napisy z tego języka. Dlatego o elementach języka L mówimy, że spełniają te kryteria lub że są syntaktycznie poprawne.

Jak już powiedzieliśmy teoria języków formalnych tworzy pewne modele obliczeń lub inaczej systemy opisu języków zwane gramatykami i automatami. Od tych systemów żąda się, aby spełniały warunki efektywności analitycznej i efektywności syntetycznej. Pierwszy z warunków oznacza, że system opisu prowadzi do algorytmu, który w skończonej liczbie kroków rozstrzyga, czy dowolne słowo należy, czy też nie należy do tego języka. Spełnienie warunku drugiego daje w rezultacie algorytm, który umożliwia wygenerowanie wszystkich słów danego języka.

Emil Leon Post (1897-1954)Zobacz biografię
Enlarge
Emil Leon Post (1897-1954)
Zobacz biografię
Gramatyka to system, którego działanie opiera się na procesie sekwencyjnego przepisywania, czyli modyfikowania pewnych napisów (słów). Przepisywanie to realizowane jest poprzez reguły przyjęte w danym systemie jako dopuszczalne. Idea ta związana jest z nazwiskami takich logików jak Axel Thue czy Emil Post. W roku 1957 Noam Chomsky, lingwista amerykański, stworzył pewien matematyczny formalizm opisu języków naturalnych zwany gramatykami generacyjnymi.

Gramatyki te opisują wybrane, najbardziej istotne cechy syntaktyczne języków, w szczególności ich strukturalne regularności.

Idee Chomsky'ego bardzo szybko przeniknęły do innych dziedzin nauki. Stworzona teoria znalazła istotne zastosowanie w badaniach nad językami programowania. Z powodzeniem gramatyki Chomsky'ego służą również do budowania modeli procesów biologicznych, czy też procesów badanych przez nauki o społeczeństwie. Teoria gramatyk rozwinęła się w wielu kierunkach, służąc jako formalny opis sekwencyjnych zmian różnorakich obiektów, takich jak, termy, grafy, obrazy, czy fraktale.

Spis treści

System przepisujący

Definicja 1.1

System przepisujący jest to para RS=(A,P), gdzie
{A} jest dowolnym skończonym zbiorem (alfabetem),
P \subseteq A^* \times A^* - skończoną relacją (zbiorem praw).

Fakt, że para (u,v) \in P zapisujemy, u~\rightarrow~v \in P i nazywamy prawem przepisywania lub produkcją w systemie RS.

Definicja 1.2

Niech RS=(A,P) będzie dowolnym systemem przepisującym, a \;\;x,y~\in~A^* dowolnymi słowami.

System RS przepisuje słowo x na słowo y (generuje y z x) bezpośrednio, co oznacza się symbolem
x~\mapsto~y,

jeśli istnieją słowa x_1 , x_2 \in A^* oraz prawo u~\rightarrow~v \in P takie, że

x = x_1 ux_2,\;\; y = x_1 vx_2.
System RS przepisuje słowo x na słowo y (generuje y z x), co oznacza się symbolem
x~\mapsto^*y,
jeśli istnieją słowa w_0 , w_1 ,..., w_k \in A^* oraz k \geq 0 takie, że
w_0~=~x, \;\; w_k~=~y,\;\;\; w_i~\mapsto~w_{i+1}\; \text{dla} \;i~=~0,1,...k-1.

Bezpośrednie wyprowadzenie "\mapsto " jest relacją na wolnym monoidzie A^*, a wyprowadzenie "\mapsto^*" zwrotnym i przechodnim domknięciem tej relacji.

Ciąg (w_0 , w_1 ,..., w_k) nazywamy wyprowadzeniem lub wywodem w systemie RS. Liczba k określa długość wyprowadzenia. Wyprowadzenie oznacza się także następująco:
w_0\mapsto~ w_1 \mapsto ~...\mapsto~w_k.


Rysunek 1

Przykład 1.1

Niech RS=(\{a,b,c\},\{(ba,ab),(ca,ac),(cb,bc)\} ) będzie systemem przepisującym. W systemie RS słowo aabbcc można wyprowadzić ze słowa cabbac (rysunek 1).

Rozważa się systemy przepisujące generujące lub rozpoznające język.

Definicja 1.3

Niech RS=(A,P) będzie dowolnym systemem przepisującym, a I dowolnym, ustalonym podzbiorem A^{*}.

  • językiem generowanym przez RS nazywamy zbiór
L_{gen}(RS,I) = \{ w \in A^* \;\;:\;\; x~\mapsto^*w \;,\; x \in I \},
  • językiem rozpoznawanym przez RS nazywamy zbiór:
L_{acc}(RS,I) = \{ w \in A^* \; \; : \; \; w~\mapsto^*x \;,\; x \in I \},

Przykład 1.2

Jeśli w przykładzie 1.1 (patrz przykład 1.1.) przyjmiemy I=\{cab \}, to

\begin{array} {l} L_{gen}(RS,I) = \{abc,acb,  cab\} \\ L_{acc}(RS,I) = \{cab,  cba\} \\ \end{array}


Axel Thue (1863-1922)Zobacz biografię
Enlarge
Axel Thue (1863-1922)
Zobacz biografię
Gramatyka, której definicję teraz wprowadzimy, jest szczególnym systemem Thuego. Można powiedzieć, że jest to system Thuego tak określony, aby poprzez wskazanie jedynie poprawnych sposobów generowania napisów definiować język. Gramatyka to jedno z najważniejszych pojęć teorii języków formalnych. Używany poniżej, dla u \in A^* i B \subset A, symbol \# _{B} u oznacza liczbę wystąpień liter z alfabetu B w słowie \textnormal{u}.

Definicja 1.4

Gramatyka jest to system G = (V_N,V_T,P,v_0), w którym

V_N \neq \emptyset - skończony zbiór symboli nieterminalnych (alfabet nieterminalny),

V_T \neq \emptyset - skończony zbiór symboli terminalnych (alfabet terminalny),

P \subseteq (V_N \cup V_T)^+ \times (V_N \cup V_T)^* - skończona relacja, zbiór produkcji (praw),

v_0 \in V_N - symbol początkowy (startowy).

Ponadto zakładamy, że V_N \cap V_T = \emptyset\;\;\; i dla każdego \;\;(u,v) \in P\;\;\; \# _{V_N} u \geq 1.

A zatem w gramatyce alfabety terminalny i nieterminalny są rozłącznymi zbiorami, a słowo u występujące po lewej stronie produkcji zawiera co najmniej jeden symbol nieterminalny. Fakt, że para (u,v) \in P, zapisujemy:
u~\rightarrow~v \in P \;\;\mbox{ lub } \;\; u~\rightarrow_G~v.

Wykorzystujemy też zdefiniowane dla systemów przepisujących pojęcia generowania bezpośredniego "\mapsto " i generowania "\mapsto^* ".

Definicja 1.5

Językiem generowanym przez gramatykę G = (V_N,V_T,P,v_0) nazywamy zbiór:

L(G) = \{ x \in V_T^*\;:\;\;v_0 \mapsto_G^* x \}.

Łatwo zauważyć, że pomiędzy językiem a generującą go gramatyką nie ma odpowiedniości wzajemnie jednoznacznej. Dany język może być generowany przez wiele gramatyk, czasem o bardzo różnej strukturze i własnościach. Stąd potrzeba wprowadzenia pojęcia równoważności językowej dla gramatyk.

Definicja 1.6

Gramatyki G_1 i G_2równoważne (językowo) wtedy i tylko wtedy, gdy L(G_1) = L(G_2).

Przykład 1.3

(1) Gramatyka G_1 = (V_N,V_T,P,v_0), w której V_N = \{v_0\}, \;\; V_T = \{a\}, \;\; P = \{ v_0 \rightarrow v_0a, \; v_0 \rightarrow a \}, generuje język
L(G_1) = \{ a^n : n = 1,2,... \}.
(2) Gramatyka G_2 = (V_N,V_T,P,v_0), w której V_N = \{v_0\}, \;\; V_T = \{a\}, \;\; P = \{ v_0 \rightarrow v_0v_0, \; v_0 \rightarrow a \}, generuje język
L(G_2) = \{ a^n : n = 1,2,... \}.
(3) Gramatyka G_{3}=\left( V_{N},V_{T},P,v_{0}\right), w której V_{N}=\left\{ v_{0},v_{1},w,w_{1},w_{2},z,z_{1},z_{2},z_{3}\right\} , \; \; V_{T}=\left\{ a,b,c\right\},
\begin{array} {r} P=  \{ v_{0}\rightarrow v_{0}z_{1},v_{0}\rightarrow v_{1}z_{1},v_{1}\rightarrow aw_{1}, v_{1}\rightarrow av_{1}w_{1}, w_{1}z_{1}\rightarrow w_{1}z_{3}, w_{1}z_{3}\rightarrow wz_{3},\\ wz_{3}\rightarrow wz,w_{1}w\rightarrow w_{1}w_{2},w_{1}w_{2}\rightarrow ww_{2},z_{2}z\rightarrow z_{1}z,  ww_{2}\rightarrow ww_{1}, zz_{1}\rightarrow z_{2}z_{1},\\ z_{2}z_{1}\rightarrow z_{2}z, w\rightarrow b,z\rightarrow c\}  \end{array}
generuje język
L(G_{3})=\left\{ a^{n}b^{n}c^{n}:n=1,2,...\right\} .
(4) Gramatyka G_4 = (V_N,V_T,P,v_0), w której V_N = \{v_0, v_1, v_2 \}, \;\; V_T = \{a,b,c\},
\begin{array} {r} P=\{v_0~\rightarrow~abc,  v_0~\rightarrow~av_1bc,  v_1b~\rightarrow~bv_1,v_1c~\rightarrow~v_2bcc, bv_2~\rightarrow~v_2b,  \\ av_2~\rightarrow~aav_1, av_2~\rightarrow~aa\}  \end{array}
generuje język
L(G_4) = \{ a^n b^n c^n : n = 1,2,... \}.

Gramatyki G_1 i G_2 są równoważne. Równoważne również są gramatyki G_3 i G_4.

Klasyfikacja Chomsky'ego

Wprowadzimy teraz cztery typy gramatyk określonych, jak powiedziano już wcześniej, przez Noama Chomsky'ego.

Definicja 2.1

Gramatyka G = (V_N,V_T,P,v_0) jest typu \textbf{(i)} dla i=0,1,2,3 wtedy i tylko wtedy, gdy spełnia następujące warunki:

typ(0): każda gramatyka, czyli system spełniajacy definicję 1.4 (patrz definicja 1.4.)
typ(1): kontekstowa, czyli gramatyka, w której każde prawo ze zbioru P ma postać
u_1 vu_2 \rightarrow u_1 xu_2,
gdzie u_1 , u_2 \in (V_N \cup V_T)^*, \; \; v \in V_N , \;\; x \in (V_N \cup V_T)^+ lub
v_0 \rightarrow 1,
przy czym, jeśli v_0 \rightarrow 1 \in P, to {v_0} nie występuje po prawej stronie w żadnym prawie z P,
typ (2): bezkontekstowa, czyli gramatyka, w której każde prawo ze zbioru P ma postać
v \rightarrow x,
gdzie v \in V_N, \;\; x \in (V_N \cup V_T)^*,
typ (3): regularna, czyli gramatyka, w której każde prawo ze zbioru P ma postać
v \rightarrow v'x\;\;\; lub \;\;\;v \rightarrow x,
gdzie v,v' \in V_N, \;\; x \in V_T^*.

Przykład 2.1

Gramatyki z przykładu 1.3 (patrz przykład 1.3.) są odpowiednio

(1) G_1 - typu (3)
(2) G_2 - typu (2)
(3) G_3 - typu (1)
(4) G_4 - typu (0)

Natomiast język L(G_1)=L(G_2) jest typu (3),
język L(G_3)=L(G_4) jest typu (1).

W oparciu o wprowadzone typy gramatyk określamy odpowiadające im rodziny (klasy) języków, oznaczając przez

\bf \mathcal{L}_{0}: - rodzinę wszystkich języków typu 0,
\bf \mathcal{L}_{1}: - rodzinę wszystkich języków typu 1, czyli języków kontekstowych,
\bf \mathcal{L}_{2}: - rodzinę wszystkich języków typu 2, czyli języków bezkontekstowych,
\bf \mathcal{L}_{3}: - rodzinę wszystkich języków typu 3, czyli języków regularnych.

Pomiędzy wprowadzonymi rodzinami języków zachodzą następujące zależności:

\bf \mathcal{L}_{3}\subseteq \! \! \! \! \! _{/\; \, }\bf \mathcal{L}_{2}\subseteq \! \! \! \! \! _{/\; \, }\bf \mathcal{L}_{1}\subseteq \! \! \! \! \! _{/\; \, }\bf \mathcal{L}_{0}

Inkluzje pierwsza i trzecia wynikają bezpośrednio z definicji odpowiednich klas języków, a więc z definicji gramatyk regularnej i bezkontekstowej oraz kontekstowej i typu (0). Natomiast fakt, że \bf \mathcal{L}_{2}\subset \bf \mathcal{L}_{1}, udowodnimy później. Podobnie z dalszych rozważań wynika, że powyższe inkluzje są właściwe.

Noam Avram Chomsky (1928-)Zobacz biografię
Enlarge
Noam Avram Chomsky (1928-)
Zobacz biografię
Gramatyki spełniają warunek efektywności syntetycznej. Systemami, które realizują warunek efektywności analitycznej, są automaty. Automaty działają w ten sposób, iż pod wpływem zewnętrznego sygnału zmieniają swój stan. W efekcie tej zmiany rozpoznają bądź nie ciągi takich sygnałów reprezentowane przez słowa. Zatem działanie automatu polega na testowaniu kolejno słów z A^{*} i określaniu, które z nich są rozpoznawane (spełniają określone kryteria), a które nie są rozpoznawane. Ogół słów rozpoznanych przez automat tworzy język rozpoznawany przez ten automat. Dla każdej z określonych powyżej rodzin języków, w sensie Chomsky'ego określa się odpowiadającą jej rodzinę automatów.

Język L jest typu (i) dla i=0,1,2,3 wtedy i tylko wtedy, gdy jest rozpoznawany przez jakiś automat z odpowiedniej rodziny. Definicje automatów i ich własności wprowadzane będą sukcesywnie przy prezentowaniu poszczególnych rodzin języków.