Wstęp do programowania / Ćwiczenia 5

<<< Powrót do głównej strony wykładu

<<< Powrót do modułu 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

0

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

1J0 S → J

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₀ → ε | 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.)