dsc00101

Automaty i Gramatyki

I rok

Imię i nazwisko:

Nr indeksu:    ..............

1. Uszereguj języki opisane przez podane wzorce od najmniejszego do największego (w sensie zawierania zbiorów).

a)	e v
1	i(ab	| ba)’(aa	1 bbyyV
i	P 1	b-y gf-
1	(abbd)*{aabby
e)	(ab\	ba)'(aa |	bby

D0 2)G3 3)lJ] 4) HO 5)C0

2. Dopasuj automaty skończone do wyrażeń regularnych opisujących akceptowane przez nie języki.

3.    [U' § Czy następująca gramatyka jest jedno

znaczna? S —• aS | Sii | e

# 0® Czy w następującej gramatyce można wy -prowadzić puste słowo? S —• uSb | -V, X — bSa | e

4.    fi'Alk Czy w następującej gratnatyce można wy

prowadzić slow) Imba? S — aSb | b.Sa | : — ~łf/l tk Czy język generowany przez następującą gramatykę jest skończony? S ■— aSb | bSa | £

Ą- |y| jf" Czy następująca gramatyka generuje pusty język? S —* SaS | bSb | o

4. |r J.    Każdy język skończony jest regularny.

Determinizacja automatu skończonego •4-    może spowodować wykładniczą eksplozję

liczby stanów.

Żeby gramatyka bezkontekstowa była jednoznaczna, to każde słowo musi mieć w niej co najwyżej jedno wyprowadzenie.

} Gramatyki liniowe opisują języki regularne.

Ls    Obliczenie automatu stosowego /noże być

nieskończone (,/apętlać się").

| tE	4	A 83 j* El —
	((o | b){a | b))'^i-	— EZE-
•V	0	+ W
fj(	(a | b)‘b	f □
	(ak)*	-V CD-
	a^+	f CD ■kEJ-

«)	Q	6
— 1	i	1
F2 i
W		a	b
-FI		2	2
T		1	1
cj	a
— 1	i	2
F2	i
d)		a	u
— 1	1.2,1
Fl
e)		«	k
-FI		2
			1

Przecięcie języków bezkontekstowyrh jest językiem bezkontekstowyin.

Suma języków regularnych jest językiem regularnym.

Jeśli języki A i ~A są częściowo obliczalne, to są obliczalne.

Język STOP jest obliczalny.

Każdy język kontekstowy jest obliczalny.

Analizator składniowy generowany przez Yacca/Bisona to rodzaj wielotaśmowej maszyny Taringa.

Analizator leksykalny generowany przez {FJLe.ya to rodzaj automatu skończonego. Parsęty LR(1) obchodzą drzewo wyprowadzenia w porządku posttikaowyni.

W parserack LL(1) tablice sterujące zawierają akcje shift i mina.

Żeby gramatyka była I.L(l), to musi być

5