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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 12: Linia 12:
 
Napisz gramatykę generującą wszystkie palindromy nad alfabetem {0,1}.
 
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">
+
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
<span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie 1</span>
 +
<div class="mw-collapsible-content" style="display:none">
 
S → &epsilon; | 0 | 1 | 0S0 | 1S1
 
S → &epsilon; | 0 | 1 | 0S0 | 1S1
  
Linia 27: Linia 29:
 
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.   
 
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>
</div>}}
+
</div>
  
 
==Zadanie 2==
 
==Zadanie 2==

Wersja z 13:19, 28 maj 2020

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

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