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

Ćwiczenia 9

Ćwiczenie 1

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

$L_{1} = {a^{n} b^{n} : n > 0}$
$L_{2} = {a^{n} b^{m} : 0 < n < m}$
$L_{3} = {a^{n} b^{m} : n, m > 0, n \neq m}$
$L_{4} = {w \in {a, b}^{*} : w = \overset{\leftarrow}{w}}$
$L_{5} = {w \in {a, b}^{*} : #_{a} w = #_{b} w}$

Rozwiązanie

Dla uproszczenia podamy tylko prawa definiowanych gramatyk, oznaczając symbol początkowy przez $v_{0}$ . Alfabety są wyznaczone przez symbole występujące w prawach.
punkt 1. $P_{1} : v_{0} \to a v_{0} b | a b$
punkt 2. $P_{2} : v_{0} \to v_{0} b | v_{1} b, v_{1} \to a v_{1} b | a b$
punkt 3.Zauważmy, że $L_{3} = L_{2} \cup L'_{2}$ gdzie $L'_{2} = {a^{n} b^{m} : 0 < m < n}$ . Wykorzystamy gramatykę z punktu 2 oraz gramatykę generującą język ${L_{2}}^{'}$
$P'_{2} : v'_{0} \to a v'_{0} | a v'_{1}, v'_{1} \to a v'_{1} b | a b$
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 - $\overline{v}$ symbolem początkowym. Do zbioru praw należą wszystkie prawa z $P_{2}$ i $P'_{2}$ oraz dwa nowe prawa.
$P_{3} : \overline{v} \to v_{0} | v'_{0}, v_{0} \to v_{0} b | v_{1} b, v_{1} \to a v_{1} b | a b, v'_{0} \to a v'_{0} | a v'_{1}, v'_{1} \to a v'_{1} b | a b$
punkt 4. $P_{4} : v_{0} \to a v_{0} a | b v_{0} b | a | b | 1$

punkt 5.

P_{5} : v_{0} \to a v_{0} b v_{0} | b v_{0} a 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 ( $v_{0}$ jest symbolem początkowym):

$(1)$

\begin{aligned} v_{0} & \to v_{0} v_{1} v_{2} | v_{2} a v_{1} v_{1} | b \\ v_{1} & \to v_{0} v_{0} | v_{1} b a | v_{2} v_{0} \\ v_{2} & \to b v_{0} a | a \end{aligned}

$(2)$

\begin{aligned} v_{0} & \to v_{1} v_{2} | v_{2} v_{4} v_{1} \\ v_{1} & \to v_{0} v_{4} | v_{1} b | a \\ v_{2} & \to b v_{0} | v_{1} a \\ v_{3} & \to a | b v_{1} \\ v_{4} & \to v_{2} v_{1} \end{aligned}

Rozwiązanie punktu 1

punktu 1. Korzystamy z algorytmu PostaćNormalnaChomsky'ego. Do zbioru nieterminali dodajemy $v_{a}$ oraz $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):

\begin{aligned} v_{0} \to v_{0} v_{1} v_{2} & : v_{0} \to v_{0} d_{1}, d_{1} \to v_{1} v_{2} \\ v_{0} \to v_{2} a v_{1} v_{1} & : v_{0} \to v_{2} d_{2}, d_{2} \to v_{a} d_{3}, d_{3} \to v_{1} v_{1} \\ v_{1} \to v_{1} b a & : v_{1} \to v_{1} d_{4}, d_{4} \to v_{b} v_{a} \\ v_{2} \to b v_{0} a & : v_{2} \to v_{b} d_{5}, d_{5} \to v_{0} v_{a} \end{aligned}

Produkcje $v_{0} \to b$ , $v_{1} \to v_{2} v_{0}$ , $v_{1} \to v_{0} v_{0}$ oraz $v_{2} \to a$ zostają bez zmian, gdyż są już w postaci normalnej Chomsky'ego. Do zbioru produkcji dodajemy jeszcze $v_{a} \to a$ oraz $v_{b} \to b$ .

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

\begin{aligned} v_{0} & \to v_{0} d_{1} | v_{2} d_{2} | b \\ v_{1} & \to v_{1} d_{4} | v_{2} v_{0} | v_{0} v_{0} \\ v_{2} & \to v_{b} d_{5} | a \\ d_{1} & \to v_{1} v_{2} \\ d_{2} & \to v_{a} d_{3} \\ d_{3} & \to v_{1} v_{1} \\ d_{4} & \to v_{b} v_{a} \\ d_{5} & \to v_{0} v_{a} \\ v_{a} & \to a \\ v_{b} & \to b \end{aligned}

Rozwiązanie punktu 2

\begin{aligned} v_{0} \to v_{2} v_{4} v_{1} & : v_{0} \to v_{2} d_{1}, d_{1} \to v_{4} v_{1} \\ v_{1} \to v_{1} b & : v_{1} \to v_{1} v_{b} \\ v_{2} \to b v_{0} & : v_{2} \to v_{b} v_{0} \\ v_{2} \to v_{1} a & : v_{2} \to v_{1} v_{a} \\ v_{3} \to b v_{1} & : v_{3} \to v_{b} v_{1} \end{aligned}

W zbiorze produkcji zostają bez zmian $v_{0} \to v_{1} v_{2}$ , $v_{1} \to v_{0} v_{4} | a$ , $v_{3} \to a$ oraz $v_{4} \to v_{2} v_{1}$ , gdyż są już w postaci Chomsky'ego. Do zbioru produkcji dodajemy jeszcze $v_{a} \to a$ , $v_{b} \to b$ .

Ćwiczenie 4

Sprowadź do postaci normalnej Greibach następującą gramatykę ( $v_{0}$ jest symbolem początkowym):

\begin{aligned} v_{0} & \to v_{2} v_{0} v_{1} | a \\ v_{1} & \to v_{0} v_{2} | v_{1} v_{2} | b \\ v_{2} & \to c \end{aligned}

Rozwiązanie

Najpierw należy sprowadzić gramatykę do postaci Chomsky'ego. W tym celu zamieniamy produkcję $v_{0} \to v_{2} v_{0} v_{1}$ na produkcje $v_{0} \to v_{2} v_{3}, v_{3} \to v_{0} v_{1}$ . Gramatyka ma więc postać:

\begin{aligned} v_{0} & \to v_{2} v_{3} | a \\ v_{1} & \to v_{0} v_{2} | v_{1} v_{2} | b \\ v_{2} & \to c \\ v_{3} & \to v_{0} v_{1} \end{aligned}

W produkcji $v_{1} \to v_{0} v_{2}$ indeks nieterminala $v_{0}$ jest niższy niż nieterminala $v_{1}$ , więc zamieniamy tę produkcję na $v_{1} \to v_{2} v_{3} v_{2} | a v_{2}$ . Następnie usuwamy lewostronną rekursje $v_{1} \to v_{1} v_{2}$ . Wyrzucamy tę produkcję, a na jej miejsce wstawiamy $v_{1} \to v_{2} v_{3} v_{2} w_{1} | a v_{2} w_{1} | b w_{1}$ oraz $w_{1} \to v_{2} | w_{1} \to v_{2} w_{1}$ .

Zamieniamy także produkcję $v_{3} \to v_{0} v_{1}$ na produkcje $v_{3} \to v_{2} v_{3} v_{1}$ i $v_{3} \to a v_{1}$ . Pierwsza z nich dalej nie spełnia warunku nałożonego na indeksy nieterminali, więc zamieniamy ją na produkcje $v_{3} \to c v_{3} v_{1}$ .

Po zakończeniu algorytmu PrzekształćDlaGreibach otrzymujemy następującą gramatykę:

\begin{aligned} v_{0} & \to v_{2} v_{3} | a \\ v_{1} & \to v_{2} v_{3} v_{2} a v_{2} | b | v_{2} v_{3} v_{2} w_{1} | a v_{2} w_{1} | b w_{1} \\ v_{2} & \to c \\ v_{3} & \to c v_{3} v_{1} | a v_{1} \\ w_{1} & \to v_{2} | v_{2} w_{1} \end{aligned}

Stosujemy teraz algorytm PostaćNormalnaGreibach. Produkcję $v_{1} \to v_{2} v_{3} v_{2}$ zamieniamy na $v_{1} \to c v_{3} v_{2}$ , a produkcję $v_{1} \to v_{2} v_{3} v_{2} w_{1}$ na $v_{1} \to c v_{3} v_{2} w_{1}$ .

Produkcję $v_{0} \to v_{2} v_{3}$ zamieniamy na $v_{0} \to c v_{3}$ .

Produkcję $w_{1} \to v_{2}$ zamieniamy na $w_{1} \to c$ , a produkcję $w_{1} \to v_{2} w_{1}$ - na $w_{1} \to c w_{1}$ .

Ostatecznie otrzymujemy gramatykę w postaci normalnej Greibach:

\begin{aligned} v_{0} & \to c v_{3} | a \\ v_{1} & \to c v_{3} v_{2} | a v_{2} | b | c v_{3} v_{2} w_{1} | a v_{2} w_{1} | b w_{1} \\ v_{2} & \to c \\ v_{3} & \to c v_{3} v_{1} | a v_{1} \\ w_{1} & \to c | c w_{1} \end{aligned}

ZADANIA DOMOWE

Ćwiczenie 5

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

$L_{6} = {a^{n} b^{m} c^{n + m} : n, m > 0}$
$L_{7} = {a^{n} b^{m} c^{k} : 0 < n, m, k; k \neq m + n}$
$L_{8} = {a^{n} b^{k} c^{n} : n \geq 0, k \geq 5}$
$L_{9} = {w \overset{\leftarrow}{w} : w \in {a, b}^{*}}$
$L_{10} = {w a^{n} b^{n} \overset{\leftarrow}{w} : n \geq 0, w \in {a, b}^{*}}$

Uwagi. Język $L_{9}$ jest właściwym podzbiorem języka palindromów $L_{4}$ rozważanego w ćwiczeniu 1. Porównaj otrzymane gramatyki.
Do znalezienia gramatyki generującej język $L_{7}$ zdefiniuj dwie gramatyki pomocnicze podobnie jak w punkcie 3 ćwiczenia 1.

Ćwiczenie 6

Sprowadź do postaci Chomsky'ego następujące gramatyki ( $v_{0}$ jest zawsze symbolem początkowym):

$(1)$

\begin{aligned} v_{0} & \to v_{0} v_{1} v_{2} v_{2} | v_{2} a v_{1} b v_{1} | v_{1} b \\ v_{1} & \to v_{0} v_{0} | a b a | a v_{1} b \\ v_{2} & \to b v_{0} a v_{1} b v_{2} a | b \end{aligned}

$(2)$

\begin{aligned} v_{0} & \to v_{1} v_{2} v_{3} | v_{2} v_{4} v_{1} \\ v_{1} & \to v_{4} a | v_{1} b v_{0} | a v_{1} v_{1} b b \\ v_{2} & \to b | a a a \\ v_{3} & \to a | b b b \\ v_{4} & \to v_{1} b b v_{3} v_{2} | a \end{aligned}

Ćwiczenie 7

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

\begin{aligned} v_{0} & \to v_{0} v_{1} | a \\ v_{1} & \to v_{1} v_{0} | b \end{aligned}

Ćwiczenie 8

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

\begin{aligned} v_{0} & \to v_{0} v_{1} | a \\ v_{1} & \to v_{0} v_{0} | v_{1} v_{0} | b \end{aligned}

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

Ćwiczenia 9

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia