Języki, automaty i obliczenia/Ćwiczenia 9: Języki bezkontekstowe i ich gramatyki

From Studia Informatyczne

Ćwiczenia 9

Ćwiczenie 1

Określ gramatyki bezkontekstowe generujące języki:

  1. \displaystyle L_1=\left\{ a^{n}b^{n}:n>0\right\},
  2. \displaystyle L_2=\left\{ a^{n}b^{m}: 0<n<m \right\},
  3. \displaystyle L_3=\left\{ a^{n}b^{m}: n,m>0, n\neq m \right\},
  4. \displaystyle L_4=\left\{ w \in \{ a,b\}^* : w = \overleftarrow{w} \right\},
  5. \displaystyle L_5=\left\{ w \in \{ a,b\}^* : \#_aw =\#_bw \right\}.

Rozwiązanie

Dla uproszczenia podamy tylko prawa definiowanych gramatyk, oznaczając symbol początkowy przez \displaystyle v_0. Alfabety są wyznaczone przez symbole występujące w prawach.
punkt 1. \displaystyle P_1 : v_0 \rightarrow a v_0 b \; |\; ab
punkt 2. \displaystyle P_2 : v_0 \rightarrow v_0 b \;|\; v_1b ,\; v_1 \rightarrow av_1b \;|\; ab
punkt 3.Zauważmy, że \displaystyle L_3=L_2 \cup L'_2 gdzie \displaystyle L'_2= \left\{ a^{n}b^{m}: 0<m<n \right\}. Wykorzystamy gramatykę z punktu 2 oraz gramatykę generującą język \displaystyle L_2'
\displaystyle P'_2 : v'_0 \rightarrow av'_0  \;|\; av'_1 ,\; v'_1 \rightarrow av'_1b \;|\; ab
Alfabety nieterminalne tych gramatyk muszą być zbiorami rozłącznymi. Alfabet nieterminalny definiowanej gramatyki jest sumą tych dwóch alfabetów z dołączonym jednym nowym symbolem -\displaystyle \overline{v} symbolem początkowym. Do zbioru praw należą wszystkie prawa z \displaystyle P_2 i \displaystyle P'_2 oraz dwa nowe prawa.
\displaystyle P_3 :\overline{v} \rightarrow v_0 \;|\; v'_0 , v_0 \rightarrow v_0 b \;|\; v_1b ,\; v_1 \rightarrow av_1b \;|\; ab,  v'_0 \rightarrow av'_0  \;|\; av'_1 ,\; v'_1 \rightarrow av'_1b \;|\; ab
punkt 4. \displaystyle P_4 : v_0 \rightarrow a v_0 a \;|\;bv_0b\;|\;a \; |\; b \;|\; 1

punkt 5. \displaystyle P_5 : v_0 \rightarrow a v_0 bv_0 \;|\; bv_0a v_0\; |\; 1

Ćwiczenie 2

Wykorzystując dowód lematu 1.2, napisz dla dowolnej gramatyki bezkontekstowej generującej język bez słowa pustego algorytm konstrukcji równoważnej gramatyki właściwej.

Ćwiczenie 3

Sprowadź do postaci Chomsky'ego następujące gramatyki (\displaystyle v_0 jest symbolem początkowym):

\mbox{(1)}

\displaystyle \aligned v_0 &\rightarrow  v_0v_1v_2\ |\ v_2av_1v_1\ |\ b \\ v_1 &\rightarrow  v_0v_0\ |\ v_1ba\ |\ v_2v_0 \\ v_2 &\rightarrow  bv_0a\ |\ a \endaligned

\mbox{(2)}

\displaystyle \aligned v_0 &\rightarrow  v_1v_2\ |\ v_2v_4v_1 \\ v_1 &\rightarrow  v_0v_4\ |\ v_1b\ |\ a \\ v_2 &\rightarrow  bv_0\ |\ v_1a \\ v_3 &\rightarrow  a\ |\ bv_1 \\ v_4 &\rightarrow  v_2v_1 \endaligned

Rozwiązanie punktu 1

punktu 1. Korzystamy z algorytmu PostaćNormalnaChomsky'ego. Do zbioru nieterminali dodajemy \displaystyle v_a oraz \displaystyle v_b. Poszczególne produkcje przekształcamy zgodnie z działaniem algorytmu (produkcja po lewej stronie dwukropka zastępowana jest zbiorem produkcji po prawej stronie dwukropka):

\displaystyle \aligned v_0 \rightarrow v_0v_1v_2\ &: v_0 \rightarrow v_0d_1, d_1  \rightarrow v_1v_2 \\ v_0 \rightarrow v_2av_1v_1\ &: v_0 \rightarrow v_2d_2, d_2  \rightarrow v_ad_3, d_3 \rightarrow v_1v_1 \\ v_1 \rightarrow v_1ba\ &: v_1 \rightarrow v_1d_4, d_4 \rightarrow v_bv_a \\ v_2 \rightarrow bv_0a\ &: v_2 \rightarrow v_bd_5, d_5 \rightarrow  v_0v_a \endaligned

Produkcje \displaystyle v_0 \rightarrow b, \displaystyle v_1 \rightarrow v_2v_0, \displaystyle v_1  \rightarrow v_0v_0 oraz \displaystyle v_2 \rightarrow a zostają bez zmian, gdyż są już w postaci normalnej Chomsky'ego. Do zbioru produkcji dodajemy jeszcze \displaystyle v_a \rightarrow a oraz \displaystyle v_b \rightarrow b.

Gramatyka w postaci normalnej Chomsky'ego wygląda więc tak:

\displaystyle \aligned v_0 &\rightarrow  v_0d_1\ |\ v_2d_2\ |\ b \\ v_1 &\rightarrow  v_1d_4\ |\ v_2v_0\ |\ v_0v_0 \\ v_2 &\rightarrow  v_bd_5\ |\ a \\ d_1 &\rightarrow  v_1v_2 \\ d_2 &\rightarrow  v_ad_3 \\  d_3 &\rightarrow  v_1v_1 \\ d_4 &\rightarrow  v_bv_a \\ d_5 &\rightarrow  v_0v_a \\ v_a &\rightarrow  a \\ v_b &\rightarrow  b \endaligned

Rozwiązanie punktu 2

\displaystyle \aligned v_0 \rightarrow v_2v_4v_1\ &: v_0 \rightarrow v_2d_1, d_1 \rightarrow v_4v_1 \\ v_1 \rightarrow v_1b\ &: v_1 \rightarrow v_1v_b \\ v_2 \rightarrow bv_0\ &: v_2 \rightarrow v_bv_0 \\ v_2 \rightarrow v_1a\ &: v_2 \rightarrow v_1v_a \\ v_3 \rightarrow bv_1\ &: v_3 \rightarrow v_bv_1 \\ \endaligned

W zbiorze produkcji zostają bez zmian \displaystyle v_0 \rightarrow v_1v_2, \displaystyle v_1  \rightarrow v_0v_4\ |\ a, \displaystyle v_3 \rightarrow a oraz \displaystyle v_4 \rightarrow  v_2v_1, gdyż są już w postaci Chomsky'ego. Do zbioru produkcji dodajemy jeszcze \displaystyle v_a \rightarrow a, \displaystyle v_b \rightarrow b.

Ćwiczenie 4

Sprowadź do postaci normalnej Greibach następującą gramatykę (\displaystyle v_0 jest symbolem początkowym):

\displaystyle \aligned v_0 &\rightarrow  v_2v_0v_1\ |\ a \\ v_1 &\rightarrow  v_0v_2\ |\ v_1v_2\ |\ b \\ v_2 &\rightarrow  c \endaligned

Rozwiązanie

Najpierw należy sprowadzić gramatykę do postaci Chomsky'ego. W tym celu zamieniamy produkcję \displaystyle v_0 \rightarrow  v_2v_0v_1 na produkcje \displaystyle v_0 \rightarrow v_2v_3, v_3 \rightarrow  v_0v_1. Gramatyka ma więc postać:

\displaystyle \aligned v_0 &\rightarrow  v_2v_3\ |\ a \\ v_1 &\rightarrow  v_0v_2\ |\ v_1v_2\ |\ b \\ v_2 &\rightarrow  c \\  v_3 &\rightarrow  v_0v_1 \endaligned

W produkcji \displaystyle v_1 \rightarrow v_0v_2 indeks nieterminala \displaystyle v_0 jest niższy niż nieterminala \displaystyle v_1, więc zamieniamy tę produkcję na \displaystyle v_1  \rightarrow v_2v_3v_2\ |\ av_2. Następnie usuwamy lewostronną rekursje \displaystyle v_1 \rightarrow v_1v_2. Wyrzucamy tę produkcję, a na jej miejsce wstawiamy \displaystyle v_1 \rightarrow v_2v_3v_2w_1\ |\ av_2w_1\ |\  bw_1 oraz \displaystyle w_1 \rightarrow v_2\ |\ w_1 \rightarrow v_2w_1.

Zamieniamy także produkcję \displaystyle v_3 \rightarrow v_0v_1 na produkcje

\displaystyle v_3 \rightarrow v_2v_3v_1 i \displaystyle v_3 \rightarrow av_1. Pierwsza z nich dalej nie spełnia warunku nałożonego na indeksy nieterminali, więc zamieniamy ją na produkcje \displaystyle v_3 \rightarrow cv_3v_1.

Po zakończeniu algorytmu PrzekształćDlaGreibach otrzymujemy

następującą gramatykę:

\displaystyle \aligned v_0 &\rightarrow  v_2v_3\ |\ a \\ v_1 &\rightarrow  v_2v_3v_2\ av_2\ |\ b\ |\ v_2v_3v_2w_1\ |\ av_2w_1\ |\ bw_1 \\ v_2 &\rightarrow  c \\ v_3 &\rightarrow  cv_3v_1\ |\ av_1 \\ w_1 &\rightarrow  v_2\ |\ v_2w_1 \endaligned

Stosujemy teraz algorytm PostaćNormalnaGreibach. Produkcję \displaystyle v_1 \rightarrow v_2v_3v_2 zamieniamy na \displaystyle v_1 \rightarrow cv_3v_2, a produkcję \displaystyle v_1 \rightarrow v_2v_3v_2w_1 na \displaystyle v_1 \rightarrow  cv_3v_2w_1.

Produkcję \displaystyle v_0 \rightarrow v_2v_3 zamieniamy na \displaystyle v_0 \rightarrow  cv_3.

Produkcję \displaystyle w_1 \rightarrow v_2 zamieniamy na \displaystyle w_1 \rightarrow c, a

produkcję \displaystyle w_1 \rightarrow v_2w_1 - na \displaystyle w_1 \rightarrow cw_1.

Ostatecznie otrzymujemy gramatykę w postaci normalnej Greibach:

\displaystyle \aligned v_0 &\rightarrow  cv_3\ |\ a \\ v_1 &\rightarrow  cv_3v_2\ |\ av_2\ |\ b\ |\ cv_3v_2w_1\ |\ av_2w_1\ |\ bw_1 \\ v_2 &\rightarrow  c \\ v_3 &\rightarrow  cv_3v_1\ |\ av_1 \\ w_1 &\rightarrow  c\ |\ cw_1 \endaligned

ZADANIA DOMOWE

Ćwiczenie 5

Określ gramatykę bezkontekstową generującą język

  1. \displaystyle L_6=\left\{ a^{n}b^{m}c^{n+m}:n,m>0\right\},
  2. \displaystyle L_7=\left\{ a^{n}b^{m}c^{k}:0<n,m,k; k\neq m+n\right\},
  3. \displaystyle L_8=\left\{ a^{n}b^{k}c^{n}:n\geq 0,k\geq 5\right\},
  4. \displaystyle L_9=\left\{ w\overleftarrow{w} : w \in \{ a,b\}^*  \right\},
  5. \displaystyle L_{10}=\left\{ wa^{n}b^{n}\overleftarrow{w}:n\geq 0, w\in \{ a,b\}^* \right\}

Uwagi. Język \displaystyle L_9 jest właściwym podzbiorem języka palindromów \displaystyle L_4 rozważanego w ćwiczeniu 1. Porównaj otrzymane gramatyki.
Do znalezienia gramatyki generującej język \displaystyle L_7 zdefiniuj dwie gramatyki pomocnicze podobnie jak w punkcie 3 ćwiczenia 1.

Ćwiczenie 6

Sprowadź do postaci Chomsky'ego następujące gramatyki (\displaystyle v_0 jest zawsze symbolem początkowym):

\mbox{(1)}

\displaystyle \aligned v_0 &\rightarrow  v_0v_1v_2v_2\ |\ v_2av_1bv_1\ |\ v_1b \\ v_1 &\rightarrow  v_0v_0\ |\ aba\ |\ av_1b \\ v_2 &\rightarrow  bv_0av_1bv_2a\ |\ b \endaligned

\mbox{(2)}

\displaystyle \aligned v_0 &\rightarrow  v_1v_2v_3\ |\ v_2v_4v_1 \\ v_1 &\rightarrow  v_4a\ |\ v_1bv_0\ |\ av_1v_1bb \\ v_2 &\rightarrow  b\ |\ aaa \\ v_3 &\rightarrow  a\ |\ bbb \\ v_4 &\rightarrow  v_1bbv_3v_2\ |\ a \endaligned

Ćwiczenie 7

Sprowadź do postaci normalnej Greibach następującą gramatykę:

\displaystyle \aligned v_0 &\rightarrow  v_0v_1\ |\ a \\ v_1 &\rightarrow  v_1v_0\ |\ b \\ \endaligned

Ćwiczenie 8

Sprowadź do postaci normalnej Greibach następującą gramatykę:

\displaystyle \aligned v_0 &\rightarrow  v_0v_1\ |\ a \\ v_1 &\rightarrow  v_0v_0\ |\ v_1v_0\ |\ b \\ \endaligned