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

← poprzednia edycja następna edycja →

WizualnieWikikod

Wersja z 16:27, 16 wrz 2006

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

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

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

@@ Linia 21: / Linia 21: @@
 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.
+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.
@@ Linia 49: / Linia 49: @@
 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 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).
@@ Linia 55: / Linia 55: @@
 ''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.
+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>}}
@@ Linia 79: / Linia 79: @@
 * <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 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>.
+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>}}
@@ Linia 90: / Linia 90: @@
 ''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>.
+''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>}}

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

Wersja z 16:27, 16 wrz 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