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

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ę

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ę

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ę

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\to 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\to v\in P$ takie, że

$x=x_{1}u{x}_2,y=x_{1}v{x}_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,\dots ,w_k\in A^{*}$ oraz $k\ge 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,\dots ,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$.

Plik:Ja-lekcja2-w-rys1

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ę

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

${\mathrm{\#}}_{B}u$

oznacza liczbę wystąpień liter z alfabetu

$B$

w słowie

$\text{u}$

.

Definicja 1.4

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

$V_N\ne \mathrm{\varnothing }$ - skończony zbiór symboli nieterminalnych (alfabet nieterminalny),

$V_T\ne \mathrm{\varnothing }$ - 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=\mathrm{\varnothing }$ i dla każdego $(u,v)\in P{\mathrm{\#}}_{V_N}u\ge 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\to v\in P\text{ lub }u{\to }_{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\underset{G}{\overset{*}{\mapsto }}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\to v_{0}a,v_0\to 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\to v_0{v}_0,v_0\to a\}$ generuje język $L(G_2)=\{a^n:n=1,2,...\}$.

(3) Gramatyka $G_3=(V_N,V_T,P,v_0)$, w której $V_N=\{v_0,v_1,w,w_1,w_2,z,z_1,z_2,z_3\},V_T=\{a,b,c\}$,

$\begin{array}{r}P=\{v_0\to v_0{z}_1,v_0\to v_1{z}_1,v_1\to a{w}_1,v_1\to a{v}_1{w}_1,w_1{z}_1\to w_1{z}_3,w_1{z}_3\to w{z}_3,\\ w{z}_3\to wz,w_{1}w\to w_1{w}_2,w_1{w}_2\to w{w}_2,z_{2}z\to z_{1}z,w{w}_2\to w{w}_1,z{z}_1\to z_2{z}_1,\\ z_2{z}_1\to z_{2}z,w\to b,z\to c\}\end{array}$

generuje język

$L(G_3)=\{a^n{b}^n{c}^n:n=1,2,...\}$.

(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\to abc,v_0\to a{v}_{1}bc,v_{1}b\to b{v}_1,v_{1}c\to v_{2}bcc,b{v}_2\to v_{2}b,\\ a{v}_2\to aa{v}_1,a{v}_2\to 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 $\text{<mrow data-mjx-texclass="ORD"><mo stretchy="false">(</mo>i<mo stretchy="false">)</mo></mrow>}$ 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}v{u}_2\to u_{1}x{u}_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\to 1$, przy czym, jeśli $v_0\to 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\to 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\to v^{\prime }xlubv\to x$, gdzie $v,v^{\prime }\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

${{ℒ}}_{\mathbf{𝟎}}$: - rodzinę wszystkich języków typu 0,

${{ℒ}}_{\mathbf{𝟏}}$: - rodzinę wszystkich języków typu 1, czyli języków kontekstowych,

${{ℒ}}_{\mathbf{𝟐}}$: - rodzinę wszystkich języków typu 2, czyli języków bezkontekstowych,

${{ℒ}}_{\mathbf{𝟑}}$: - 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:

${{ℒ}}_{\mathbf{𝟑}}\mathbf{\subseteq }{}_{/}{{ℒ}}_{\mathbf{𝟐}}\mathbf{\subseteq }{}_{/}{{ℒ}}_{\mathbf{𝟏}}\mathbf{\subseteq }{}_{/}{{ℒ}}_{\mathbf{𝟎}}$

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 ${{ℒ}}_{\mathbf{𝟐}}\mathbf{\subset }{{ℒ}}_{\mathbf{𝟏}}$ udowodnimy później. Podobnie z dalszych rozważań wynika, że powyższe inkluzje są właściwe.

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.