39826 IMAGE2

a)	a	b
- FI	1	2
2	3
3	2	1

Cfe ^a+1^b*

| C\ (aa | bb)^m [~T{ b^mab*ab*

m w*

■\h | (o | b(m)*aby

a

u cg

10

□

Uszereguj języki opisane przez podane notce od najmniejszego do największego <"w sensie sanriersora iblorów).

*) €

b)    a*y | b*m*

c)    aCtb

d)    (e j a | 6, ” c) (a | 6)?

>)(J | ²)[2j} 3)[T] 4)ul s)Hal

)opasuj automaty skończone do wzorców općsoją-ych akceptowane przez nie języki.

b)	a	b
— 1	2	1
2	3	2
F 3 c)	a	3 b
-4 1	2	3
F 2	2
F3		3
d)	a	b
-* 1	2	3
F 2	1	3
3	3	3

)	a	6
- F 1	3	2
2		1
3	1

Czy    gramatyka jest jedno-

osaczaa* 5 — <łS> Stb ! t Ozy w rtastąpiąjąoęj gramatyce 3504^* wyprowadzić słowo aahaJ

§ — AA>'    i

Ozy w następującej gramatyce marna wyprowadzić poste słowo?

n —* S S o o**    6

r^~ Czy języ k generowany przez następu-jęcą gramatykę jest skończony? 5 —♦ \Sj SbS a

Ozy rvasręp«ąjąGa gramatyka generuje pu-'    sśy jęty k? > — *51 | 6

^r    Automaty stosowe rotpoznają    języki

---beskomtekscowe.

f    ;    Dopełnienie języka regularnego jest języ-

*—    kkn regularnym.

r    ^    Każdy język kontekstowy    jest

beakontekszowr.

c^THT Suma jęjy kow bej kontekstowych jest ję-

----*    zyidem bezkontekstowym.

Każdy język bezlcontekstowy jest regu-lamy.

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

Jeśli gramatyka bezkontekstowa jest jed-ocffiiłacama, to nie występuje w niej lewostronna rekursja.

Determiniaaoa automatu skończonego może spowodować wykładniczą eksplozję Uciby 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 parsem LR(1) nie może się udać dla gramatyki niejednoznacznej. Yacc i Bison implementują mechanizm