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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Pch (dyskusja | edycje)
411 edycji
Pch (dyskusja | edycje)
411 edycji
Linia 47: Linia 47:
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 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 żą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 <math>1^m0^m</math>, ponieważ x ma tę postać (z założenia indukcyjnego).
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).

Wersja z 17:23, 18 gru 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 0n1m0n+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ą fw. Przyglądając się pierwszej pozycji j>0, dla której fw(j)=0, zauważamy, że słowa w2...wj−1 oraz wj+1...wn są poprawnymi wyrażeniami nawiasowymi o mniejszej długości. Zatem można uzyskać wyprowadzenie słowa w S→(S)S→⋯→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

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=67660”