Plik
źródłowy: C:\Jurek\www\wsb-wdi\0405\04cwE-gramatyki.doc;
Data: 2005-07-14 11:58
Zad. 1. Dana jest gramatyka bezkontekstowa zawierająca następujące produkcje:
1) S ® A B
2) A ® 1
3) A ® 1 A
4) B ® 0
5) B ® 0 B
Podaj wywód ciągu 110 na podstawie tej
gramatyki.
Zad. 2. Uzupełnij poniższe produkcje tak, aby otrzymać gramatykę równoważną
gramatyce z zad. 1:
1) S ® 1 S
2) S ® 1 Z
3) Z ® ...
4) Z ® ...
Zad. 3. Napisz gramatykę bezkontekstową (zbiór produkcji) opisującą język (01)+0.
Zad. 4. Napisz wyrażenie regularne opisujące język z zad. 1.
Zad. 5. Dana jest gramatyka bezkontekstowa zawierająca następujące produkcje:
1) S ® C Q
2) C ® 0
3) C ® 1
4) C ® 2
5) C ® 3
6) C ® 4
7) C ® 5
8) C ® 6
9) C ® 7
Q jest symbolem terminalnym. Napisz
program w AWK, który bada, czy pierwsze pole jest zbudowane zgodnie z tą
gramatyką i jeśli tak, to ma się pojawić w tym wierszu OK., a w przeciwnym
przypadku trzy znaki zapytania. Na przykład dla pliku:
1
1Q
powinniśmy dostać
???
OK.
Zad. 6. Dana jest gramatyka bezkontekstowa
1) S ® 0 S 1
2) S ® !
Które z poniższych ciągów należą do
języka opisanego tą gramatyką?
!
0!1
0011
000!1
000!111
!0011
11!00
Zad. 7. Uruchom pokazany na wykładzie program napisany metodą zejść rekurencyjnych, który rozpoznaje, czy na wejściu jest ciąg zer i jedynek zakończony spacją. Zaproponuj przypadki testowe (dane wejściowe i spodziewane wyniki).
Zad. 8. Napisz program metodą zejść rekurencyjnych dla gramatyki z zad. 6. Dla uproszczenia załóż, że po badanym ciągu zawsze występuje spacja. Przetestuj napisany program korzystając m.in. z danych z zad. 6.