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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
(Zadanie 1½)
(Przenumerowanie)
Linia 29: Linia 29:
 
</div>  
 
</div>  
  
==Zadanie ==
+
==Zadanie 2==
 
Napisz gramatykę generującą język wszystkich słów nad alfabetem {0,1} postaci <math>0^n1^m0^{n+m}</math>.
 
Napisz gramatykę generującą język wszystkich słów nad alfabetem {0,1} postaci <math>0^n1^m0^{n+m}</math>.
  
Linia 59: Linia 59:
 
</div>
 
</div>
  
==Zadanie 2 (wyrażenia nawiasowe)==
+
==Zadanie 3 (wyrażenia nawiasowe)==
 
Napisz gramatykę generującą wszystkie poprawne wyrażenia nawiasowe.
 
Napisz gramatykę generującą wszystkie poprawne wyrażenia nawiasowe.
  
Linia 98: Linia 98:
 
</div>
 
</div>
  
==Zadanie 3==
+
==Zadanie 4==
 
Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że <math>\#_0(w)=\#_1(w)</math>
 
Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że <math>\#_0(w)=\#_1(w)</math>
  
Linia 108: Linia 108:
 
''Zgodność'': oczywista.
 
''Zgodność'': oczywista.
  
''Pełność'': podobnie jak w Zadaniu 2. 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>.
+
''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.
 
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>
Linia 120: Linia 120:
 
''Zgodność'': oczywista
 
''Zgodność'': oczywista
  
''Pełność'': podobnie jak w Rozwiązaniu 1 i w Rozwiązaniu 2 Zadania 2.
+
''Pełność'': podobnie jak w Rozwiązaniu 1 i w Rozwiązaniu 2 Zadania 3.
 
</div>
 
</div>
 
</div>
 
</div>
  
==Zadanie 4==
+
==Zadanie 5==
 
Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że <math>\#_0(w)=\#_1(w)+1</math>
 
Podaj gramatykę języka słów w nad alfabetem {0,1} takich, że <math>\#_0(w)=\#_1(w)+1</math>
  
Linia 136: Linia 136:
 
symbol startowy: N
 
symbol startowy: N
  
''Zgodność'': wiedząc (z Zadania 3), ż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.
+
''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 3, 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.
+
''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>
 
</div>
 
</div>
Linia 149: Linia 149:
 
-->
 
-->
  
==Zadanie 5==
+
==Zadanie 6==
 
Podaj gramatykę generującą liczby w zapisie binarnym, które są podzielne przez 3.
 
Podaj gramatykę generującą liczby w zapisie binarnym, które są podzielne przez 3.
  
Linia 190: Linia 190:
 
</div>
 
</div>
  
==Zadanie 6==
+
==Zadanie 7==
 
Podaj gramatykę generującą słowa nad alfabetem {0,1}, w których nie występuje podsłowo 000.
 
Podaj gramatykę generującą słowa nad alfabetem {0,1}, w których nie występuje podsłowo 000.
  
Linia 241: Linia 241:
 
'''Dla ciekawskich '''   
 
'''Dla ciekawskich '''   
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Język opisany w tym zadaniu (i w Zadaniu 5) 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ę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.)
 
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>
 
</div>
 
</div>

Wersja z 16:33, 19 lip 2006

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 1

Zadanie 2

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

Rozwiązanie 1

Zadanie 3 (wyrażenia nawiasowe)

Napisz gramatykę generującą wszystkie poprawne wyrażenia nawiasowe.

Rozwiązanie 1

Rozwiązanie 2

Zadanie 4

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

Rozwiązanie 1

Rozwiązanie 2

Zadanie 5

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

Rozwiązanie 1

Zadanie 6

Podaj gramatykę generującą liczby w zapisie binarnym, które są podzielne przez 3.

Rozwiązanie 1

Pytanko 1

Odpowiedź

Zadanie 7

Podaj gramatykę generującą słowa nad alfabetem {0,1}, w których nie występuje podsłowo 000.

Rozwiązanie 1

Rozwiązanie 2

Rozwiązanie 3

Dla ciekawskich