89079 IMAGE3

Sr ittdeksu:

Uszereguj języki opisane przez podane wzorce od _Qirnniejszego do największego (w sensie zawierania sbiorów).

a)    (a*6*)⁺

b)    a* fbft*

c)    %/

^d^(a⁺6⁺)*

/*)    (aó)*

*>□ UQ «)□ so

| Czy następująca grumntyka jest jednoznaczna? S -■* a Sn | bSb | e □ Czy iw następującej    gramatyce

można wyprowadzić puste słowo? S • SaX | Xh_} X -* 06 | $

GEL Qzy w następującej    gramatyce

,mQŻna wyprowadzić słowo abab? / S —* nSa | bSb | r

| Czy Język generowany przez następującą gramatykę Jest    skończony?

S-> XXX_S X a\b

2 Dopasuj automaty skończone do wzorców opisujących akceptowane przez nie języki.

a)	a	b
— 1	2	3
F 2	2
F 3		3
b)	a	b
— i	2	1
2	3	2
F 3		3
V'5	a	b
— 1	2	3
F 2	1	3
3	3	3

d)

e\

	a	6
—* F 1	3	2
2		1
3	1
	a	b
— FI	1	2
2	3
3	2	1

Czy następująca gramatyka generuje pusty język? S -■* abS | SbS \ a

Dopełnienie każdego Języka bezkontek-stowego jest językiem bezkontekstowym. Sklejenie Języków regularnych jest językiem regularnym.

Każdy Język częściowo obliczalny jest obliczalny.

Gramatyki ogólne (typu 0) opisują języki częściowo obliczalne.

Gramatyki liniowe opisują języki regularne.

nr

t r® □ 4 CD

być

Automat stosowy deterministyczny.

Lewostronna faktoryzaęja powoduje, że gramatyku bezkontekstowa staje się jednoznaczna.

Eliminacja r-prząjść w automacie skończonym może spowodować wykładniczą eksplozję liczby jego stanów.

Leksem jest reprezentowany przez parę: żeton, atrybut.

Analizator leksykalny stara się, przede wszystkim, rozpoznać teksem pasujący do jak najwcześniejszą) reguły w specyfiku-

jj!

Parsery [SJLR(l) odtwarzają drzewo wyprowadzenia od korzenia do liści. Analizator leksykalny generowany przez [F]Lexa to rodzaj nledeterministycsnego automatu stosowego.

Parsery LL(1) obchodzą drzewo wyprowadzenia w porządku prefiksowym,

Yocc 1 Bison implementują mechanizm atrybutów syntezowanych.

Konstrukcja parsom LL(1) nie może się udać dla gramatyki niejednoznacznej.

musi