Informatyka MIMUW

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.

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.

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.

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.

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

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

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}\)

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 \({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:/p>

\(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_2\) są ró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:

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.

Gramatyki spełniają warunek efektywności syntetycznej. Systemami, które realizują warunek fektywnoś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.