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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 53: Linia 53:
 
''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.
 
''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 zauważyć, ż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>
 
</div>}}
 
</div>}}
Linia 77: Linia 77:
 
* <math>f_w(n)=0</math>
 
* <math>f_w(n)=0</math>
 
* <math>f_w(i)\ge0</math> dla <math>i=0\dots n</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>
 
</div>}}
 
</div>}}

Wersja z 21:05, 15 lis 2006

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

0

Zadanie 2

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

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ą . Przyglądając się pierwszej pozycji j>0, dla której , zauważamy, że słowa oraz są poprawnymi wyrażeniami nawiasowymi o mniejszej długości. Zatem można uzyskać wyprowadzenie słowa w .

Zadanie 4

Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że

Rozwiązanie 1

0S1

Rozwiązanie 2

1S0S

Zadanie 5

Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że

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

S00

Ćwiczenie 1

{{{3}}}

Odpowiedź

S11 S1 → 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

S01

Rozwiązanie 2

S01

Rozwiązanie 3

0

Dla ciekawskich

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Wstęp_do_programowania_/_Ćwiczenia_3&oldid=66054”