Języki, automaty i obliczenia/Ćwiczenia 2: Gramatyka jako model obliczen. Hierarchia Chomsky'ego

From Studia Informatyczne

Ćwiczenia 2

Ćwiczenie 1

Niech RS=(\{a,b,c\},\{(a,b),(b,c),(b,a),(cc,b)\}) będzie systemem przepisującym. Sprawdź, czy w systemie tym można przepisać bezpośrednio słowo x na słowo y, jeśli x=abc, y=aab.

Rozwiązanie

Zauważmy, że |x|=|y|. Ponieważ każde prawo przepisuje słowo na słowo o tej samej lub krótszej długości, musielibyśmy użyć praw b \mapsto a oraz c \mapsto b, ale tego drugiego nie ma w zbiorze praw. Zatem słowa abc nie da się przepisać bezpośrednio na słowo aab.

Ćwiczenie 2

Zdefiniujmy zbiory: A=\{a,b,c\} oraz

P=\{(aabc,ac),(aa,aaca),(bc,cc),(aa,baab),(bc,ab),(aabc,bbaacc)\}.

Udowodnij, nie obliczając w sposób bezpośredni, że w systemie przepisującym RS=(A, P) nie da się przepisać pośrednio słowa w=aabcbcaaaabcaabc na słowo v=abc.

Rozwiązanie

Słowo {w} ma parzystą ilość liter, a {v} - nieparzystą. Każda reguła przepisuje słowo o parzystej długości w słowo o parzystej długości, więc nie można przepisać słowa {w} w słowo {v}.

Ćwiczenie 3

Niech A=\{a,b,c\}. Rozważmy system przepisujący RS=(A,\{(a,b),(b,a)\}) i określmy na zbiorze wszystkich k-elementowych słów nad alfabetem A binarną relację \rho_k  \subseteq A^k \times A^k w następujący sposób:

\forall u, v \in A^k\ u \rho_k v \Leftrightarrow u \mapsto^* v.
(1) Pokaż, że \rho_k jest relacją równoważności
(2) Udowodnij, że ind \rho_k = 2^k (to znaczy, że relacja \rho_k ma 2^k klas abstrakcji)

Rozwiązanie punktu 1

  • Zwrotność: Słowo {u można przepisać na słowo {u} w zerowej liczbie kroków.

  • Symetryczność: Jeśli {u} da się przepisać na słowo {w} zamieniając pewne litery {a} na {b} (lub na odwrót), to wychodząc ze słowa {v} i dokonując przepisania w tych samych miejscach otrzymamy słowo {u}.

  • Przechodniość: Jeśli {u} można przepisać na {v}, a {v} na {w}, to {u} można przepisać na {w}: u \mapsto^* v \mapsto^* w, czyli u \mapsto^* w.

Wskazaówka do punktu 2

Zauważ, że w dowolny sposób można zamieniać litery {a} na {b} oraz {b} na {a}, natomiast litery {c} nigdy się nie zmienią w inne litery, gdyż nie ma żadnej reguły, która by na to pozwalała.

Rozwiązanie punktu 2

Kluczową obserwacją jest fakt, że jeśli w słowie {u} występują na pewnych pozycjach litery {c}, to podczas procesu przepisywania zawsze pozostaną na swoim miejscu. Zmieniać się mogą natomiast, w dowolny sposób, podsłowa słowa {u} nie zawierające liter {c}. Zatem każda klasa abstrakcji relacji \rho_k złożona jest ze wszystkich słów, które mają tę samą ilość liter {c} na tych samych pozycjach. Ponieważ jest {k} liter i każda z nich może być literą {c} lub nie, zatem istnieje {2^k} możliwych sposobów rozmieszczenia liter {c} w {k}-elementowym słowie.

Przykładowo, jeśli k=3, to istnieje 2^3=8 klas abstrakcji relacji \rho_3: ***, c**, *c*, **c, cc*, c*c, *cc, ccc, gdzie {*} oznacza dowolny ze znaków {a, b}. Na przykład przedostatnia klasa abstrakcji zawiera dwa słowa: acc oraz bcc.

Ćwiczenie 4

Określ języki L_{gen}(RS,I) generowane przez system przepisujący RS=(A,P) oraz zbiór I \subseteq A^*, jeśli:

(1) A=\{a,b\}, P=\{(a,aa),(a,b)\}, I=\{a\},
(2) A=\{a\}, P=\{(aa,aaaaa), (aaa, aa)\}, I=\{a, a^5, a^{12}\},
(3) A=\{a,b,c\}, P=\{(ab,ba),(c,aa),(aaa,ac)\}, I=\{cc,  abc\}.

Rozwiązanie do punktu 1

Oczywiście a \in L_{gen}(RS, I). Zauważmy, że stosując tylko pierwsze prawo możemy przekształcić słowo {a} w słowo {a^n} dla dowolnego n naturalnego, a następnie dowolne litery tego słowa zamienić, używając drugiego prawa, na litery {b}. Zatem językiem generowanym przez ten system jest A^+.

Rozwiązanie do punktu 2

Zauważmy, że możemy ze słowa {a^n} o długości \geq 3 uzyskać słowo a^k dla 2 \leq k \leq n, stosując n-k-krotnie prawo (aaa,aa). Zauważmy też, że stosując do słowa a^5 \in Ik-krotnie prawo (aa,aaaaa), możemy otrzymać słowo a^{5+3k}. Łącząc obie te obserwacje, dochodzimy do wniosku, że L_{gen}(RS, I)=A^+. Słowo a^p możemy wygenerować w następujący sposób: najpierw zastosować w dowolnym miejscu słowa a^p pierwsze prawo k razy, gdzie k spełnia warunek 5+3k \geq p, a następnie stosować prawo drugie (również w dowolnym miejscu wygenerowanego słowa) dopóki jego długość jest większa od {p}. Ponieważ najkrótsze możliwe w ten sposób do wygenerowania słowo to a^2 oraz a \in I, otrzymujemy, że L_{gen}(RS, I)=\{a, a^2, a^3, ...\}=A^+.

Rozwiązanie do punktu 3

Generowany język obliczymy ręcznie, biorąc najpierw zbiór X_0=I i iteracyjnie stosując do zbioru X_i wszystkie możliwe prawa do wszystkich słów z tego zbioru. Procedurę tę powtarzamy, dopóki da się wygenerować jakieś nowe słowo. Jeśli w pewnym kroku j+1 nic nowego nie wygenerujemy, tzn. jeśli X_{j+1}=X_j, procedurę przerywamy i mamy L_{gen}(RS, I)=X_j. Proces generacji przedstawiony jest na rysunku 1. Etykiety krawędzi wskazują które prawo zostało użyte do wygenerowania danego słowa. Rozwiązaniem jest
L_{gen}(RS, I)=\{cc, aac, abc, aca, bac, caa,  aaaa, abaa, baaa\}.

<flash>file=Ja-lekcja2-c-rys1.swf|width=350|height=350</flash>

Rysunek 1

Ćwiczenie 5

Określ języki L_{acc}(RS,I) rozpoznawane przez system przepisujący RS=(A,P) oraz zbiór I \subseteq A^*, jeśli:

(1) A=\{a\}, P=\{(aaa, a), (aa, aaa)\}, I=\{a, aa\},
(2) A=\{a,b,c\}, P=\{(a,bb),(a,ccc)\}, I=\{abc, a^2b^2c^2, a^3b^3c^3, ... \}.

Rozwiązanie punktu 1

Musimy określić zbiór słów, które, da się przekształcić przez prawa (aaa, a) oraz (aa, aaa) do słowa {a} lub aa. Oczywiście a \in L_{acc}(RS, I), aa \in L_{acc}(RS, I). Zauważmy, że dla dowolnego p>2 słowo a^p można przekształcić, stosując tylko pierwsze prawo do słowa postaci {a} (jeśli p jest nieparzyste) lub aa (jeśli {p} jest parzyste). Zatem L_{acc}(RS, I)=A^+ (stosowanie drugiego prawa nic już nie zmieni; wystarczy stosować prawo pierwsze).

Rozwiązanie punktu 2

L_{acc}(RS, I)=I \cup \{a^{11k}:\ k \in \mathds{N}\} \cup \{a^pb^qa^r: 11|2p+2r+q\} \cup \{a^pc^qa^r: 11|3p+q+3r\} \cup \{a^pb^qa^rc^sa^t: \exists p_a,p_b,r_b,r_c:\ p=p_a+p_b, r=r_b+r_c, p_a=2p_b+q+2r_b=3r_c+s+3t\}.

Litera {a} może przejść w trzy litery {c} lub dwie litery {b}. Podzielmy słowo {a^n} na trzy podsłowa u_a, u_b oraz u_c:
a^n=u_au_bu_c.
Każdą literę {a} słowa u_c zamienimy na ccc, a każdą literę słowa u_b - w słowo bb. Ponieważ liczba liter {a}, {b} i {c} w przekształconym słowie jest taka sama, to 3|u_c|=2|u_b|=|u_a|. Stąd wynika, że |u_a| jest podzielne przez 6. Zatem jeśli u_a=a^{6k}, to
a^n=a^{6k}a^{3k}a^{2k}=a^{11k}.

Uzasadnimy teraz, że \{a^pb^qa^r: 11|2p+2r+q\} \subset L_{acc}(RS,I). Niech p=p_a+p_b, r=r_b+r_c. p_b liter a stojących tuż przed pierwszą literą b oraz r_b liter a stojących bezpośrednio za ostatnią literą b przekształcimy w sumie na p_b+r_b słów bb. Do pierwszych p_a liter a nie będziemy stosować żadnej produkcji. Ostatnie r_c liter a zamienimy na r_c słów ccc. Aby w ostatecznie wyprodukowanym słowie liczba liter a,b,c była taka sama, musi zachodzić p_a=2p_b+q+2r_b=3r_c, a więc 3|p_a. Niech p_a=3k. Wtedy r_c=k i skoro p_b=p-3k oraz r_b=r-k, to 11k=2p+2r+q.
Do pozostałych dwóch zbiorów stosujemy analogiczną argumentację.

Ćwiczenie 6

Jaki język generuje gramatyka G=(V_N, V_T, P, v_0), jeśli:

(1) V_N=\{v_0,v_1,v_2\}, V_T=\{a,b\},
    P=\{v_0 \rightarrow v_1v_0v_2, v_0 \rightarrow ab, v_1 \rightarrow a, v_2 \rightarrow b\},
(2) V_N=\{v_0,v_1\}, V_T=\{a,b\},
    P=\{v_0\rightarrow v_1v_0, v_0 \rightarrow bv_1, v_1 \rightarrow v_1v_1, v_1 \rightarrow a\},

Rozwiązanie punktu 1

Z pierwszej produkcji możemy wygenerować ciąg v_1^nv_0v_2^n, gdzie n \geq 0. Stosując następnie produkcję drugą otrzymamy v_1^nabv_2^n. Teraz możemy już tylko zamienić każde {v_1} na {a}, a każde {v_2} na {b}. Gramatyka generuje więc słowa postaci a^nb^n,\ n \geq 1.

Rozwiązanie punktu 2

Pierwsze dwie produkcje pozwalają na wygenerowanie ciągu v_1^kbv_1, gdzie k \geq 0. Produkcja trzecia pozwala na "namnożenie" dowolnej ilości nieterminali {v_1}, a czwarta zamienia wszystkie {v_1} na {a}. Gramatyka generuje więc język L=\{a^kba^l,\ k \geq 0, l \geq 1\}.

Ćwiczenie 7

Podaj gramatykę która generuje język:

(1) L_1=\{a^nb^mc^{m+n}: m,n \geq 0\},
(2) L_2=\{a^{2^n}: n \geq 0\},
(3) L_3=\{w: \sharp_aw=2\cdot \sharp_bw\},
(4) L_4=\{w=a_1a_2...a_n: a_i \in \{a,b\} \wedge\forall 1 \leq j \leq n\ \sharp_ba_1a_2...a_j \leq\sharp_aa_1a_2...a_j \leq  \sharp_ba_1a_2...a_j + 3\},
(5) \bigstar \ L_5=\{a^{n^2}: n \geq 1\}.

Podajemy przykładowe gramatyki.

Rozwiązanie punktu 1

Podamy dwie gramatyki generujące język L_1.
a) V_N=\{v_0,  v_1\}, V_T=\{a, b, c\}, P=\{v_0 \rightarrow 1, v_0 \rightarrow av_0c, v_0 \rightarrow bv_1c, v_1 \rightarrow bv_1c, v_1 \rightarrow 1\}.
Przy pomocy produkcji drugiej generujemy a^nv_0c^n. Stosując produkcję trzecią, a następnie {m} razy produkcję czwartą dostajemy słowo a^n b^mv_1c^{n+m}. Przy pomocy produkcji z 1 po prawej stronie likwidujemy symbol nieterminalny, jak również dostajemy słowa z języka L_1 dla {n=0} lub {m=0}.
b) V_N=\{v_0, t, u, w, x, v_a, v_b\}, V_T=\{a, b, c\}, P=\{v_0 \rightarrow xt, t \rightarrow v_atc,, t \rightarrow v_btc, v_bv_a \rightarrow v_av_b, t \rightarrow u, v_bu \rightarrow ub, v_au \rightarrow wa, v_aw \rightarrow wa, xw \rightarrow 1\}.

Pierwsze trzy produkcje pozwalają na wygenerowanie ciągu postaci xrtc^{|r|}, gdzie {r} jest dowolnym słowem złożonym z nieterminali v_a i v_b, przy czym ich łączna ilość równa jest liczbie terminali {c} występujących po prawej stronie {t}. Czwarta produkcja zamienia {t} na {u}. Nieterminal {u} może zniknąć tylko wtedy, gdy znajdzie się obok nieterminala {x} (ostatnia produkcja). Należy więc "przepchnąć" go przez wszystkie nieterminale v_a oraz v_b, ale produkcje 6-8 pozwalają zrobić to tylko wtedy, gdy każde v_a występuje przed każdym v_b. Przy okazji, podczas wędrówki {u} na początek słowa, każde v_a (odpowiednio v_b) zostaje zamienione na terminal {a} (odpowiednio {b}). W rezultacie gramatyka wygeneruje tylko słowa postaci a^nb^mc^{m+n}, gdzie m,n \geq 0.

Rozwiązanie punktu 2

V_N=\{v_0, v_1, v_2\}, V_T=\{a\}, P=\{v_0  \rightarrow a, v_0 \rightarrow v_1v_0, v_1 \rightarrow av_2, v_1a \rightarrow aav_1, v_1v_2 \rightarrow v_2, v_1v_2  \rightarrow 1\}.

Pierwsza produkcja pozwala wygenerować słowo a^{2^0}=a. W celu wygenerowania słowa a^{2^k} należy k-krotnie zastosować produkcję drugą, a następnie produkcję trzecią. Otrzymamy wtedy słowo v_1^kav_2. Aby teraz pozbyć się wszystkich {v_1}, należy przeprowadzić je na koniec słowa i zastosować przedostatnią produkcję (przy ostatnim {v_1} należy zastosować produkcję ostatnią, by pozbyć się także nieterminala {v_2}). Produkcja czwarta gwarantuje, że po przeprowadzeniu każdego {v_1} z lewej na prawą stronę słowa, ilość liter {a} wzrośnie dwukrotnie. Zatem po przeprowadzeniu k nieterminali {v_1} i usunięciu ich oraz nieterminala {v_2} otrzymamy słowo a^{2^k}.

Rozwiązanie punktu 3

V_N=\{v_0,v_a,v_b\}, V_T=\{a, b\}, P=\{v_0->v_0v_av_av_b, v_0 \rightarrow v_av_av_b, v_av_b  \rightarrow v_bv_a, v_bv_a \rightarrow v_av_b, v_a \rightarrow  a, v_b \rightarrow b\}.

Zastosowanie pierwszych dwóch produkcji pozwala na wygenerowanie ciągu nieterminali C=(v_av_av_b)^n. Nieterminali v_a jest więc dwa razy więcej niż v_b. Trzecia i czwarta produkcja pozwalają na swobodną zamianę kolejności nieterminali v_a i v_b w słowie C a dwie ostatnie produkcje służą do zamiany nieterminali na terminale.

Rozwiązanie punktu 4

Zauważmy, że język L_4 złożony jest ze słów {w} o następującej własności: w każdym prefiksie słowa {w} liter {a} jest co najmniej tyle co liter {b}, a co najwyżej o 3 więcej niż liter {b}. Gramatyka będzie generowała słowa od lewej do prawej (L_4 jest językiem regularnym). Nieterminal a_i oznacza, że w danym momencie wygenerowano o {i} liter {a} więcej niż {b}. W ten sposób możemy kontrolować, aby powyższa zależność pomiędzy ilością liter {a} i {b} została zachowana.

V_N=\{v_0,a_0,a_1,a_2,a_3\}, V_T=\{a, b\}, P=\{v_0 \rightarrow  aa_1, v_0 \rightarrow a, a_1 \rightarrow ba_0, a_1 \rightarrow  aa_2, a_1 \rightarrow a, a_1 \rightarrow b, a_2 \rightarrow  ba_1, a_2 \rightarrow aa_3, a_2 \rightarrow a, a_2 \rightarrow  b, a_3 \rightarrow ba_2, a_3 \rightarrow b\}.

Rozwiązanie punktu 5

V_N=\{s, t, u, w, x, y\}, V_T=\{a\}, P=\{s \rightarrow ytx, t \rightarrow utw, t \rightarrow uw, uw \rightarrow wau, ua \rightarrow au, ux \rightarrow x, ya  \rightarrow ay, yw \rightarrow y, yx \rightarrow 1\}.

Idea działania gramatyki jest następująca: najpierw generujemy słowo postaci yu^nw^nx, używając do tego celu produkcji pierwszej, drugiej i trzeciej. Każdy nieterminal {u} przeprowadzimy na prawą stronę za pomocą produkcji czwartej i piątej. Pozbywamy się nieterminala {u} za pomocą produkcji szóstej. Każde {u} "przechodząc" przez nieterminal {w} wnosi do słowa jeden terminal {a}. Zatem każdy z k nieterminali {u} "wyprodukuje" k terminali {a}, w sumie uzyskamy więc k^2 terminali {a}. Aby pozbyć się na końcu wszystkich nieterminali, przeprowadzimy na prawą stronę nieterminal {y} używając produkcji siódmej i ósmej. Dzięki produkcji ósmej pozbędziemy się wszystkich nieterminali {w}. Zauważmy, że {y} nie usunie żadnego nieterminala {u} (nie ma takiej produkcji), zatem zanim rozpoczniemy przesuwanie {y} na prawą stronę, musimy pozbyć się wszystkich {u}. To gwarantuje, że wygenerujemy wszystkie k^2 terminali a. Ostatnia produkcja usuwa dwa ostatnie nieterminale {y} i {x}.

Ćwiczenie 8

Podaj gramatykę, która generuje język poprawnych wyrażeń arytmetycznych zbudowanych z operatorów dodawania i mnożenia oraz jednego argumentu oznaczonego symbolem a. Przykładem takiego wyrażenia może być np. a+a \cdot a.

Rozwiązanie

Przykładowa gramatyka może wyglądać tak: G=(V_N, V_T,  P, v_0), gdzie V_N=\{v_0\}, V_T=\{a,+,\cdot\}, a zbiór produkcji ma postać:
P=\{v_0 \rightarrow v_0+v_0,\ v_0 \rightarrow v_0 \cdot  v_0,\ v_0 \rightarrow a\}.

ZADANIA DOMOWE

Ćwiczenie 9

Niech RS=(\{a,b,c\},\{(a,b),(b,c),(b,a),(cc,b)\}) będzie systemem przepisującym. Sprawdź, czy w systemie tym można przepisać bezpośrednio słowo {x} na słowo {y}, jeśli:

(1) x=aabbcc, y=bacbb,
(2) x=baccaa, y=cbbba.

Ćwiczenie 10

Określ język L_{gen}(RS,I) generowany przez system przepisujący RS=(A,P) oraz zbiór I \subseteq A^*, jeśli A=\{a,b\}, P=\{(bb,a)\}, I=\{b, b^2, b^3, ...\}.

Ćwiczenie 11

Jaki język generuje gramatyka G=(V_N, V_T, P, v_0), jeśli:

(1) V_N=\{v_0,v_1,v_2,v_3\}, V_T=\{a,b\},
     P=\{v_0 \rightarrow v_1v_3, v_1 \rightarrow av_1b, v_1 \rightarrow av_2b, v_2 \rightarrow bv_2a,
     v_2 \rightarrow ba, v_3 \rightarrow av_3b, v_3 \rightarrow  ab\},
(2) V_N=\{v_0\}, V_T=\{a,b\},
     P=\{v_0 \rightarrow v_0v_0, v_0 \rightarrow av_0b, v_0 \rightarrow bv_0a, v_0 \rightarrow ab, v_0 \rightarrow ba\}

Ćwiczenie 12

Podaj gramatykę, która generuje język:

(1) L_2=\{a^nb^{2n}: n \geq 0\},
(2) L_4=\{a^kba^lba^m: k,l,m \geq 1\},
(3) L_5=\{w: \sharp_a w=\sharp_b w\},
(4) L_8=\{ww: w \in \{a,b\}^+\}.

Ćwiczenie 13

Określ, do jakich klas (możliwie najwęższych) należą gramatyki, które generują języki z zadań 1.7 oraz 1.12.

Ćwiczenie 14

Załóżmy, że poprawny adres e-mailowy składa się z następujących elementów: niepustego identyfikatora złożonego z samych liter maksymalnie z czterech), znaku "małpy", niepustej nazwy serwera złożonej z samych liter (maksymalnie czterech), kropki oraz dwuliterowej nazwy domeny. Załóżmy, że alfabet składa się tylko z liter {a}, {b} i {c}. Poprawnym adresem e-mailowym jest np. adres babc@aaa.cc. Zbuduj gramatykę, która generuje wszystkie poprawne adresy e-mailowe.