23327 IMAGE6

&

JE \ HFl

s.yfn

□

Mm

□

6. o

4-(B

MS

-/osa

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

a)    |

b)    o*6* | &•<*•

c)    aH6

1 (« | o 1 6)+

| 11 6)?

|p| »>o »□ «>□ »)□

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

*)	a	i
P FI	1	2
“Tl	|
3	2	1

b)	a	6
— 1	2	1
2	3	2
F 3		3
c)	a	6
— 1	2	3
F 2	2
F 3		3
d)	a	6
l	2	3
F2	1	3
3	3	3
e)		a	6
-*F 1		3	2
2			1
3		1

^pi «⁺i‘⁺ i. P (aa I **)*

^ 130 b‘ab'ab‘

Md. I (oa)*o

^[CTI (a | 6(aa)*a6)*

] Osy następująca gramatyka jest jedno-nacnuT 5 —* aSb | 566 j e J Cary w następującej gramatyce można wyprowadzić słowo aaba7 5 —• aaS i 566 | 6

Jjiy} Czy w następującej gramatyce mocna wyprowadzić puste słowo? 5 —» SS | cS6 | 6

Czy język generowany przez następującą gramatykę jest skończony? 5 — 65 a ( 565 | a

f j/V ; Czy następująca gramatyka generuje pusty język? 5 —+ aSb J 6

Automaty stosowe rozpoznają języki beskontekstowe.

Dopełnienie języka regularnego jest językiem regularnym.

Każdy język kontekstowy jest beskontekstowy.

Suma języków bezkontekstowych jest językiem bezkontekstowym.

Każdy język bezkontekstowy jest regularny.

Analizator leksykalny stara się przede wszystkim dopasować jak najdłuższy leksem.

Jeśli gramatyka bezkontekstowa jest jednoznaczna, to nie występuje w niej lewostronna rekurąja.

Determinizacja automatu skończonego może spowodować wykładniczą eksplozję liczby stanów.

Automat stosowy w każdym kroku wczytuje dokładnie jeden znak.

Żeton reprezentuje parę: leksem, atrybut.

W parserach LL(1) drzewo wyprowadzenia jest odtwarzane od korzenia do liści. Parsery LR(1) obchodzą drzewo wyprowadzenia w porządku prefiksowym. Analizator składniowy generowany przez Yacc^ła/Bison^ła to rodzaj deterministycznego automatu stosowego.

Konstrukcja par sera LR(1) nie może się udać dla gramatyki niejednoznacznej. Yacc i Bison implementują mechanizm atrybutów dziedziczonych.