Wstęp do programowania / Ćwiczenia 3: Różnice pomiędzy wersjami

← poprzednia edycja następna edycja →

WizualnieWikikod

Wersja z 12:33, 7 sie 2006

<<< 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 \dots \to w$ .

Zadanie 4

Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że $#_{0} (w) = #_{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 $#_{0} (w) = #_{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

Wstęp do programowania / Ćwiczenia 3: Różnice pomiędzy wersjami

Wersja z 12:33, 7 sie 2006

Spis treści

Zadanie 1 (palindromy)

Zadanie 2

Zadanie 3 (wyrażenia nawiasowe)

Zadanie 4

Zadanie 5

Zadanie 6 (liczby podzielne przez 3)

Zadanie 7

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
+{{powrot|Wstęp do programowania| do głównej strony wykładu}}
+{{powrot|modul_5|do modułu 5}}
+To są ćwiczenia z gramatyk bezkontekstowych.
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+Ogladaj rozwiązania __SHOWALL__<br>
+Ukryj rozwiązania __HIDEALL__
+</div>
+==Zadanie 1 (palindromy)==
+Napisz gramatykę generującą wszystkie palindromy nad alfabetem {0,1}.
+{{rozwiazanie|||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S → &epsilon; | 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 → &epsilon;, 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 &epsilon;,  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.
+</div>
+</div>}}
+==Zadanie 2==
+Napisz gramatykę generującą język wszystkich słów nad alfabetem {0,1} postaci <math>0^n1^m0^{n+m}</math>.
+{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+J → &epsilon; | 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 <math>1^m0^m</math> oraz że każde słowo wyprowadzone z S jest postaci <math>0^n1^m0^{n+m}</math>.
+Przypadek bazowy: wyprowadzenie długości 1 jest możliwe tylko z J i rzeczywiście wyprowadzone słowo &epsilon; jest postaci <math>1^m0^m</math> (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 <math>1^m0^m</math>, a więc również <math>0^n1^m0^{n+m}</math> (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 <math>0^n1^m0^{n+m}</math>, zatem <math>0x0=0^{n+1}1^m0^{n+m+1}</math>, 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 <math>1^m0^m</math>, 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 <math>1^m0^m</math> można wyprowadzić z J. Następnie przez indukcję po n, że każde słowo postaci <math>0^n1^m0^{n+m}</math> można wyprowadzić z S.
+Istotnie, jeśli m=0 to słowo <math>1^00^0=\epsilon</math> można wyprowadzić z J. Zakładając, że słowo <math>1^m0^m</math> można wyprowadzić z J, łatwo widać, że wyprowadzenie J → 1J0 →...→ 11<sup>m</sup>0<sup>m</sup>0 jest wyprowadzeniem słowa <math>1^{m+1}0^{m+1}</math>. Podobnie łatwo pokazać, że każde słowo postaci <math>0^n1^m0^{n+m}</math> da się wyprowadzić z S.
+</div>
+</div>}}
+==Zadanie 3 (wyrażenia nawiasowe)==
+Napisz gramatykę generującą wszystkie poprawne wyrażenia nawiasowe.
+{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S → SS | (S) | &epsilon;
+''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 &epsilon; 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&isin;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&isin;L, stąd uv&isin;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 &epsilon;) da się wyprowadzić.
+Niech w będzie dowolnym wyrażeniem nawiasowym o długości n>0. Określmy funkcję <math>f_w(i)=\#_((w_1...w_i)-\#_)(w_1...w_i)</math>, czyli różnicę w liczbie wystąpień nawiasu otwierającego i zamykającego w prefiksie o długości i. Łatwo zauważyć, że:
+* <math>f_w(0)=0</math>
+* <math>f_w(n)=0</math>
+* <math>f_w(i)\ge0</math> dla <math>i=0\dots n</math>
+W przypadku gdy istnieje j takie, że <math>0<j<n</math> i <math>f_w(j)=0</math> słowa <math>w_1...w_j</math> oraz <math>w_{j+1}...w_n</math> są poprawnymi wyrażeniami nawiasowymi o długości mniejszej niż n. Zatem istnieją wyprowadzenia <math>S \rightarrow \cdots \rightarrow w_1...w_j</math> oraz <math>S \rightarrow \cdots \rightarrow w_{j+1}...w_n</math> i da się z nich złożyć wyprowadzenie <math>S \rightarrow SS \rightarrow \cdots \rightarrow w</math>.
+W przypadku, gdy dla wszystkich j, <math>f_w(j)>0</math> słowo <math>w_2...w_{n-1}</math> jest poprawnym wyrażeniem nawiasowym o długości n-2, zatem wyprowadzalnym z S. Stąd łatwo otrzymać wyprowadzenie słowa w <math>S \rightarrow (S) \rightarrow \cdots \rightarrow w</math>.
+</div>
+</div>}}
+{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S → (S)S | &epsilon;
+''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ą <math>f_w</math>. Przyglądając się '''pierwszej''' pozycji j>0 dla której <math>f_w(j)=0</math>, zauważamy, że słowa <math>w_2...w_{j-1}</math> oraz <math>w_{j+1}...w_n</math> są poprawnymi wyrażeniami nawiasowymi o mniejszej długości. Zatem można uzyskać wyprowadzenie słowa w <math>S \rightarrow (S)S \rightarrow \cdots \rightarrow w</math>.
+</div>
+</div>}}
+==Zadanie 4==
+Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że <math>\#_0(w)=\#_1(w)</math>
+{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S → SS | 0S1 | 1S0 | &epsilon;
+''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 <math>f_w(i)=\#_0(w_1...w_i)-\#_1(w_1...w_i)</math>.
+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.
+</div>
+</div>}}
+{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S → 0S1S | 1S0S | &epsilon;
+''Zgodność'': oczywista
+''Pełność'': podobnie jak w Rozwiązaniu 1 i w Rozwiązaniu 2 Zadania 3.
+</div>
+</div>}}
+==Zadanie 5==
+Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że <math>\#_0(w)=\#_1(w)+1</math>
+{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+R → 0R1 | 1R0 | RR | &epsilon;
+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.
+</div>
+</div>}}
+<!--
+R → 0R1R | 1R0R | &epsilon;
+N → 0N1R | 0R1N | 1N0R | 1R0N | 0
+symbol startowy: N
+-->
+==Zadanie 6 (liczby podzielne przez 3)==
+Podaj gramatykę generującą liczby w zapisie binarnym, które są podzielne przez 3.
+{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S<sub>0</sub> → 0 | S<sub>0</sub>0 | S<sub>1</sub>1
+S<sub>1</sub> → 1 | S<sub>0</sub>1 | S<sub>2</sub>0
+S<sub>2</sub> → S<sub>1</sub>0 | S<sub>2</sub>1
+symbol startowy: S<sub>0</sub>
+''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<sub>1</sub> → S<sub>2</sub>0. Jeśli (z założenia indukcyjnego)  S<sub>2</sub> wygeneruje liczbę w o reszcie 2, to wygenerowana przez S<sub>1</sub> 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<sub>i</sub>. 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.
+</div>
+</div>}}
+{{cwiczenie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+Jak należy zmodyfikować tę gramatykę, aby generowane liczby binarne nie mogły zaczynać się od 0 ?
+</div>
+</div>}}
+{{odpowiedz||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S<sub>0</sub> → S<sub>0</sub>0 | S<sub>1</sub>1
+S<sub>1</sub> → 1 | S<sub>0</sub>1 | S<sub>2</sub>0
+S<sub>2</sub> → S<sub>1</sub>0 | S<sub>2</sub>1
+S → S<sub>0</sub> | 0
+symbol startowy: S
+</div>
+</div>}}
+==Zadanie 7==
+Podaj gramatykę generującą słowa nad alfabetem {0,1}, w których nie występuje podsłowo 000.
+{{rozwiazanie| 1||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S<sub>0</sub> → &epsilon; | S<sub>0</sub>1 | S<sub>1</sub>1 | S<sub>2</sub>1
+S<sub>1</sub> → S<sub>0</sub>0
+S<sub>2</sub> → S<sub>1</sub>0
+S → S<sub>0</sub> | S<sub>1</sub> | S<sub>2</sub>
+symbol startowy: S
+Zgodność i pełność tej gramatyki wynika z faktu, że S<sub>j</sub> generuje wszystkie słowa w nie zawierające 000 i kończące się na j zer.
+</div>
+</div>}}
+{{rozwiazanie| 2||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+S<sub>0</sub> → &epsilon; | S<sub>0</sub>1 | S<sub>0</sub>01 | S<sub>0</sub>001
+S → S<sub>0</sub> | S<sub>0</sub>0 | S<sub>0</sub>00
+symbol startowy: S
+Ta gramatyka powstała z poprzedniej przez usunięcie symboli S<sub>1</sub> i S<sub>2</sub> i włączenie ich (pojedynczych) produkcji do produkcji pozostałych symboli.
+</div>
+</div>}}
+{{rozwiazanie| 3||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> <div class="mw-collapsible-content" style="display:none">
+Z → &epsilon; | 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
+</div>
+</div>}}
+<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+'''Dla ciekawskich '''
+<div class="mw-collapsible-content" style="display:none">
+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.)
+</div>
+</div>