Wstęp do programowania / Ćwiczenia 5

To są ćwiczenia z gramatyk bezkontekstowych.

Ogladaj rozwiązania __SHOWALL__
Ukryj rozwiązania __HIDEALL__

Zadanie 1 (palindromy)

Napisz gramatykę generującą wszystkie palindromy nad alfabetem {0,1}.

Rozwiązanie 1

S → ε | 0 | 1 | 0S0 | 1S1

Zgodność: (każde wygenerowane słowo jest palindromem) Dowód przez indukcję po długości wyprowadzenia.

Przypadek bazowy: wyprowadzenie długości 1. Są 3 przypadki: S → ε, S → 0, S → 1. Wszystkie wygenerowane słowa są palindromami.

Krok indukcyjny: załóżmy że wszystkie wyprowadzenia długości < n (dla danego n>1) są zgodne. Weźmy dowolne wyprowadzenie S →...→ x długości n. Wyprowadzenie to może zaczynać się od produkcji S → 0S0 lub S → 1S1. W pierwszym przypadku x=0y0, a z jego wyprowadzenia łatwo odczytać wyprowadzenie S →...→ y o długości n-1. Z założenia indukcyjnego y jest palindromem, zatem jest nim również słowo x=0y0. Analogicznie dowodzimy zgodność wyprowadzenia zaczynającego się od produkcji S → 1S1.

Pełność: (każdy palindrom da się wygenerować) Dowód przez indukcję po długości słowa.

Przypadek bazowy: jeśli słowo ma długość 0 lub 1, to jest to ε, 0 lub 1. Wszystkie te słowa dają się wygenerować.

Krok indukcyjny: jeśli palindrom x ma długość > 1, to jest postaci 0y0 lub 1y1, gdzie y jest palindromem o mniejszej dlugości. Z założenia indukcyjnego S →...→ y. Zatem S → 0S0 →...→ 0y0 lub S → 1S1 →...→ 1y1 i otrzymaliśmy wyprowadzenie słowa x.

Zadanie 2

Napisz gramatykę generującą język wszystkich słów nad alfabetem {0,1} postaci $0^{n}1^{m}0^{n+m}$.

Rozwiązanie 1

J → ε | 1J0

S → J | 0S0

symbol startowy: S

Zgodność: (każde wygenerowane słowo należy do języka) pokażemy przez indukcję po długości wyprowadzenia, że każde słowo wyprowadzone z J jest postaci $1^{m}0^{m}$ oraz że każde słowo wyprowadzone z S jest postaci $0^{n}1^{m}0^{n+m}$.

Przypadek bazowy: wyprowadzenie długości 1 jest możliwe tylko z J i rzeczywiście wyprowadzone słowo ε jest postaci $1^{m}0^{m}$ (dla m=0).

Krok indukcyjny: załóżmy, że wszystkie wyprowadzenia o długości < n (dla pewnego n>1) spełniają tę własność. Weźmy dowolne wyprowadzenie o długości n. Jego pierwszym krokiem jest S → J, S → 0S0 lub J → 1J0,

W pierwszym przypadku wyprowadzenie zawiera wyprowadzenie o długości n-1 startujące z J. Z założenia indukcyjnego wiemy, że wyprowadzone słowo jest postaci $1^{m}0^{m}$, a więc również $0^{n}1^{m}0^{n+m}$ (dla n=0).

W drugim przypadku wyprowadzone słowo jest postaci 0x0, gdzie x jest wyprowadzalny z S za pomocą n-1 kroków. Zatem z założenia indukcyjnego x jest postaci $0^{n}1^{m}0^{n+m}$, zatem $0x0=0^{n+1}1^{m}0^{n+m+1}$, zatem jest też jest tej postaci.

W trzecim przypadku wyprowadzone słowo jest postaci 1x0, gdzie x można wyprowadzić z J w n-1 krokach, zatem podobnie jak poprzednio 1x0 jest postaci $1^{m}0^{m}$, ponieważ x ma tę postać (z założenia indukcyjnego).

Pełność: (każde słowo języka da się wyprowadzić). Najpierw przez indukcję po m pokażemy, że każde słowo postaci $1^{m}0^{m}$ można wyprowadzić z J. Następnie przez indukcję po n, że każde słowo postaci $0^{n}1^{m}0^{n+m}$ można wyprowadzić z S.

Istotnie, jeśli m=0 to słowo $1^{0}0^{0}=\epsilon$ można wyprowadzić z J. Zakładając, że słowo $1^{m}0^{m}$ można wyprowadzić z J, łatwo widać, że wyprowadzenie J → 1J0 →...→ 11^m0^m0 jest wyprowadzeniem słowa $1^{m+1}0^{m+1}$. Podobnie łatwo pokazać, że każde słowo postaci $0^{n}1^{m}0^{n+m}$ da się wyprowadzić z S.

Zadanie 3 (wyrażenia nawiasowe)

Napisz gramatykę generującą wszystkie poprawne wyrażenia nawiasowe.

Rozwiązanie 1

S → SS | (S) | ε

Zgodność: (każde wygenerowane słowo jest poprawnym wyrażeniem nawiasowym) Niech L oznacza język poprawnych wyrażeń nawiasowych. Dowód zgodności przez indukcję po długości wyprowadzenia.

Przypadek bazowy: poprzez wyprowadzenie długości 1 jest możliwe wygenerowanie tylko słowa ε i należy ono do L.

Krok indukcyjny: każde dłuższe wyprowadzenie zaczyna się od produkcji S → (S) lub S → SS. W pierwszym przypadku wygenerowane słowo będzie postaci (w), gdzie S →...→ w jest wyprowadzeniem o długości n-1, czyli w∈L z założenia indukcyjnego.

Podobnie w drugim przypadku, wygenerowane słowo będzie postaci uv, gdzie S →...→ u oraz S →...→ v są wyprowadzeniami o długości mniejszej niż n (suma długości tych wyprowadzeń wynosi n-1). Zatem u,v∈L, stąd uv∈L.

Pełność: (każde wyrażenie nawiasowe da się wyprowadzić) Dowód przez indukcję po długości wyrażenia. Wyrażenie o długości 0 (słowo puste ε) da się wyprowadzić.

Niech w będzie dowolnym wyrażeniem nawiasowym o długości n>0. Określmy funkcję $f_{w}(i)=\#_{(}(w_{1}...w_{i})-\#_{)}(w_{1}...w_{i})$, czyli różnicę w liczbie wystąpień nawiasu otwierającego i zamykającego w prefiksie o długości i. Łatwo zauważyć, że:

• $f_{w}(0)=0$
• $f_{w}(n)=0$
• $f_{w}(i)\geq 0$ dla $i=0\dots n$

W przypadku gdy istnieje j takie, że $0<j<n$ i $f_{w}(j)=0$ słowa $w_{1}...w_{j}$ oraz $w_{j+1}...w_{n}$ są poprawnymi wyrażeniami nawiasowymi o długości mniejszej niż n. Zatem istnieją wyprowadzenia $S\rightarrow \cdots \rightarrow w_{1}...w_{j}$ oraz $S\rightarrow \cdots \rightarrow w_{j+1}...w_{n}$ i da się z nich złożyć wyprowadzenie $S\rightarrow SS\rightarrow \cdots \rightarrow w$.

W przypadku, gdy dla wszystkich j, $f_{w}(j)>0$ słowo $w_{2}...w_{n-1}$ jest poprawnym wyrażeniem nawiasowym o długości n-2, zatem wyprowadzalnym z S. Stąd łatwo otrzymać wyprowadzenie słowa w $S\rightarrow (S)\rightarrow \cdots \rightarrow w$.

Rozwiązanie 2

S → (S)S | ε

Zgodność: oczywista.

Pełność: podobnie jak w Rozwiązaniu 1. Dla uzyskania danego słowa w o długości > 0 należy posłużyć się funkcją $f_{w}$. Przyglądając się pierwszej pozycji j>0 dla której $f_{w}(j)=0$, zauważamy, że słowa $w_{2}...w_{j-1}$ oraz $w_{j+1}...w_{n}$ są poprawnymi wyrażeniami nawiasowymi o mniejszej długości. Zatem można uzyskać wyprowadzenie słowa w $S\rightarrow (S)S\rightarrow \cdots \rightarrow w$.

Zadanie 4

Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że $\#_{0}(w)=\#_{1}(w)$

Rozwiązanie 1

S → SS | 0S1 | 1S0 | ε

Zgodność: oczywista.

Pełność: podobnie jak w Zadaniu 3. Dla uzyskania słowa w o długości n należy przyjrzeć się wykresowi funkcji $f_{w}(i)=\#_{0}(w_{1}...w_{i})-\#_{1}(w_{1}...w_{i})$. Jeśli funkcja ta nie ma miejsc zerowych poza 0 i n, pierwszą produkcją jest S → 0S1 lub S → 1S0. W przeciwnym przypadku w rozkłada się na dwa krótsze słowa o równej liczbie zer i jedynek i pierwszą produkcją jest S → SS.

Rozwiązanie 2

S → 0S1S | 1S0S | ε

Zgodność: oczywista

Pełność: podobnie jak w Rozwiązaniu 1 i w Rozwiązaniu 2 Zadania 3.

Zadanie 5

Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że $\#_{0}(w)=\#_{1}(w)+1$

Rozwiązanie 1

R → 0R1 | 1R0 | RR | ε

N → 0N1 | 1N0 | RN | NR | 0

symbol startowy: N

Zgodność: wiedząc (z Zadania 4), że R generuje słowa o równej liczbie 0 i 1, łatwo pokazać przez indukcję, że N generuje słowa, w których liczba 0 jest o jeden większa niż liczba 1.

Pełność: mając dane słowo w o długości > 1 zaczynamy od wskazania (dowolnego) nadmiarowego 0. Następnie postępujemy jak w Zadaniu 4, nie licząc wskazanego 0, pamiętając przy tym, żeby ta część słowa, która zawiera wskazane 0, była wyprowadzana z N, a nie z R.

Zadanie 6

Podaj gramatykę generującą liczby w zapisie binarnym, które są podzielne przez 3.

Rozwiązanie 1

S₀ → 0 | S₀0 | S₁1

S₁ → 1 | S₀1 | S₂0

S₂ → S₁0 | S₂1

symbol startowy: S₀

Zgodność: Łatwo pokazać, że kolejne symbole generują liczby, które w dzieleniu przez 3 mają resztę odpowiednio 0, 1 i 2. Dwa przypadki bazowe są oczywiste, następnie weźmy na przykład produkcję S₁ → S₂0. Jeśli (z założenia indukcyjnego) S₂ wygeneruje liczbę w o reszcie 2, to wygenerowana przez S₁ liczba w0 będzie miała resztę 2×2 mod 3 = 1. Podobnie można sprawdzić wszystkie pozostałe produkcje.

Pełność: Przez indukcję po długości liczby pokażemy, że każdą liczbę o reszcie z dzielenia przez 3 wynoszącej i da się wygenerować z symbolu S_i. Istotnie, dla liczb jednocyfrowych jest to oczywiste. Dla pozostałych, postaci wb, wystarczy popatrzeć na ostatnią cyfrę b. Reszta z dzielenia wb przez 3 oraz wartość b determinują resztę z dzielenia w przez 3. Dla wszystkich sześciu przypadków w naszej gramatyce istnieje odpowiednia produkcja. Następnie wystarczy użyć założenia indukcyjnego, aby wygenerować w.

Pytanko 1

Jak należy zmodyfikować tę gramatykę, aby generowane liczby binarne nie mogły zaczynać się od 0 ?

Odpowiedź

S₀ → S₀0 | S₁1

S₁ → 1 | S₀1 | S₂0

S₂ → S₁0 | S₂1

S → S₀ | 0

symbol startowy: S

Zadanie 7

Podaj gramatykę generującą słowa nad alfabetem {0,1}, w których nie występuje podsłowo 000.

Rozwiązanie 1

S₀ → ε | S₀1 | S₁1 | S₂1

S₁ → S₀0

S₂ → S₁0

S → S₀ | S₁ | S₂

symbol startowy: S

Zgodność i pełność tej gramatyki wynika z faktu, że S_j generuje wszystkie słowa w nie zawierające 000 i kończące się na j zer.

Rozwiązanie 2

S₀ → ε | S₀1 | S₀01 | S₀001

S → S₀ | S₀0 | S₀00

symbol startowy: S

Ta gramatyka powstała z poprzedniej przez usunięcie symboli S₁ i S₂ i włączenie ich (pojedynczych) produkcji do produkcji pozostałych symboli.

Rozwiązanie 3

Z → ε | 0 | 00

S → Z | S1Z

symbol startowy: S

Z - krotki ciąg zer (mniej niż 3)

S - ciąg krótkich ciągów zer poprzedzielanych jedynkami

Dla ciekawskich

Język opisany w tym zadaniu (i w Zadaniu 6) jest w istocie językiem regularnym, czyli dającym się wygenerować bez rekurencji, a tylko poprzez iterację (czyli prostszym, niż zwykły język bezkontekstowy). Można to poznać po tym, że udało nam się stworzyć gramatykę, w której wszystkie produkcje są postaci X → Yz lub X → Y gdzie X i Y to symbole nieterminalne, a z to symbol terminalny.

Języki regularne mają wiele wspólnego z wyrażeniami regularnymi używanymi w prostych operacjach na tekstach, takich jak wyszukiwanie i zastępowanie (np przez programy Unixowe grep, sed itp.)