Wstęp do programowania / Ćwiczenia 3

<<< Powrót do modułu Gramatyki - definiowanie składni i semantyki wyrażeń

To są ćwiczenia z gramatyk bezkontekstowych.

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i 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 żądanej 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=ϵ$ można wyprowadzić z J. Zakładając, że słowo $1^m{0}^m$ można wyprowadzić z J, łatwo zauważyć, ż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)

Rozwiązanie 2

ε

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\to (S)S\to \cdots \to w$.

Zadanie 4

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

Rozwiązanie 1

0S1

Rozwiązanie 2

1S0S

Zadanie 5

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

Rozwiązanie 1

1R0

Zadanie 6 (liczby podzielne przez 3)

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

Rozwiązanie 1

S₀0

Ćwiczenie 1

{{{3}}}

Odpowiedź

S₁1 S₁ → 1

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₀1

Rozwiązanie 2

S₀1

Rozwiązanie 3

0

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.)