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

Ć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:

$\mathrm{\forall }u,v\in A^{k}u{\rho }_{k}v\iff 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 $\ge 3$ uzyskać słowo $a^k$ dla $2\le k\le 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\ge 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\}$.

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^2{b}^2{c}^2,a^3{b}^3{c}^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 \mathbb{\mathbb{N}}\}\cup \{a^p{b}^q{a}^r:11|2p+2r+q\}\cup$ $\{a^p{c}^q{a}^r:11|3p+q+3r\}\cup$ $\{a^p{b}^q{a}^r{c}^s{a}^t:\mathrm{\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_a{u}_b{u}_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^p{b}^q{a}^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\to v_1{v}_0{v}_2,v_0\to ab,v_1\to a,v_2\to b\}$,

(2) $V_N=\{v_0,v_1\}$, $V_T=\{a,b\}$,
    $P=\{v_0\to v_1{v}_0,v_0\to b{v}_1,v_1\to v_1{v}_1,v_1\to a\}$,

Rozwiązanie punktu 1

Z pierwszej produkcji możemy wygenerować ciąg $v_1^n{v}_0{v}_2^n$, gdzie $n\ge 0$. Stosując następnie produkcję drugą otrzymamy $v_1^{n}ab{v}_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^n{b}^n,n\ge 1$.

Rozwiązanie punktu 2

Pierwsze dwie produkcje pozwalają na wygenerowanie ciągu $v_1^{k}b{v}_1$, gdzie $k\ge 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^{k}b{a}^l,k\ge 0,l\ge 1\}$.

Ćwiczenie 7

Podaj gramatykę która generuje język:

(1) $L_1=\{a^n{b}^m{c}^{m+n}:m,n\ge 0\}$,

(2) $L_2=\{a^{2^n}:n\ge 0\}$,

(3) $L_3=\{w:{\mathrm{♯}}_{a}w=2\cdot {\mathrm{♯}}_{b}w\}$,

(4) $L_4=\{w=a_1{a}_2...a_n:a_i\in \{a,b\}\wedge$$\mathrm{\forall }1\le j\le n{\mathrm{♯}}_b{a}_1{a}_2...a_j\le {\mathrm{♯}}_a{a}_1{a}_2...a_j\le {\mathrm{♯}}_b{a}_1{a}_2...a_j+3\}$,

(5) $★L_5=\{a^{n^2}:n\ge 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\to 1$, $v_0\to a{v}_{0}c$, $v_0\to b{v}_{1}c$, $v_1\to b{v}_{1}c$, $v_1\to 1\}$.
Przy pomocy produkcji drugiej generujemy $a^n{v}_0{c}^n$. Stosując produkcję trzecią, a następnie $m$ razy produkcję czwartą dostajemy słowo $a^n{b}^m{v}_1{c}^{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\to xt$, $t\to v_{a}tc$,, $t\to v_{b}tc$, $v_b{v}_a\to v_a{v}_b$, $t\to u$, $v_{b}u\to ub$, $v_{a}u\to wa$, $v_{a}w\to wa$, $xw\to 1\}$.

Pierwsze trzy produkcje pozwalają na wygenerowanie ciągu postaci $xrt{c}^{|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^n{b}^m{c}^{m+n}$, gdzie $m,n\ge 0$.

Rozwiązanie punktu 2

$V_N=\{v_0,v_1,v_2\}$, $V_T=\{a\}$, $P=\{v_0\to a$, $v_0\to v_1{v}_0$, $v_1\to a{v}_2$, $v_{1}a\to aa{v}_1$, $v_1{v}_2\to v_2$, $v_1{v}_2\to 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^{k}a{v}_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_0{v}_a{v}_a{v}_b$, $v_0\to v_a{v}_a{v}_b$, $v_a{v}_b\to v_b{v}_a$, $v_b{v}_a\to v_a{v}_b$, $v_a\to a$, $v_b\to b\}$.

Zastosowanie pierwszych dwóch produkcji pozwala na wygenerowanie ciągu nieterminali $C=(v_a{v}_a{v}_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\to a{a}_1$, $v_0\to a$, $a_1\to b{a}_0$, $a_1\to a{a}_2$, $a_1\to a$, $a_1\to b$, $a_2\to b{a}_1$, $a_2\to a{a}_3$, $a_2\to a$, $a_2\to b$, $a_3\to b{a}_2$, $a_3\to b\}$.

Rozwiązanie punktu 5

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

Idea działania gramatyki jest następująca: najpierw generujemy słowo postaci $y{u}^n{w}^{n}x$, 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\to v_0+v_0,v_0\to v_0\cdot v_0,v_0\to 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\to v_1{v}_3,v_1\to a{v}_{1}b,v_1\to a{v}_{2}b,v_2\to b{v}_{2}a$,
     $v_2\to ba,v_3\to a{v}_{3}b,v_3\to ab\}$,

(2) $V_N=\{v_0\}$, $V_T=\{a,b\}$,
     $P=\{v_0\to v_0{v}_0,v_0\to a{v}_{0}b,v_0\to b{v}_{0}a,v_0\to ab,v_0\to ba\}$

Ćwiczenie 12

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

(1) $L_2=\{a^n{b}^{2n}:n\ge 0\}$,

(2) $L_4=\{a^{k}b{a}^{l}b{a}^m:k,l,m\ge 1\}$,

(3) $L_5=\{w:{\mathrm{♯}}_{a}w={\mathrm{♯}}_{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.