IMAGE9

; ^9

f

Imię i nazwisko; Nr indeksu: ____

Automaty i Gramatyki Egzamin poprawkowy 2000/3010

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

b)    arb* | 6*o*    \

c)    / o n 6

p I a | 6)⁺

/ e)    fp | b)7

o te*)□ <)□»)[: i

♦    Ą

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

di

a)	a	b
— FI	1	2
2	3
3	2	l

■7

iM

ip

b)	a	6
— 1	2	1
2	3	2
F 3		3
c)	a	6
— 1	2	3
F 2	2
F3		3
d)	a	6
— 1	2	3
F 2	1	3
3	3	3

•| H ^a+i⁶⁺

[g] (oo | bb)*

I (j | b*ab*ab*

0] (««)*« i

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

llśfi

i

sO

-> ©

2

I li

□

■/ffi

□

□

? 1^1

i

re

Czy następująca gramatyka Jest Jednoznaczna? S a.S'(ł | S66 | e (!*y w następującej gramatyce umAua wyprowadzić słowo uabai S * iia.Y | tlbb | b

Czy w następujęcej gramatyce moAna wyprowadzić puste słowo? S i | oSb | b

C 'nv Język gunerowany przez następującą gramatyki, jest skończony? S — bSn | $bi | o

Cty następująca gramatyka generuje pusty Język? S ■ -* aSb | b

Automaty stosowe rozpoznaję Języki bezkonto lutowe.

Dopełnienie Języka regularnego Jest językiem regularnym.

KnAdy Język kontekstowy Jest bezkonte lutowy.

Surnn Języków bczkontekstowych jest Ję-syklem bezkontekstowym.

KnAdy Język bezkontekztowy jest regularny.

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

JnAll gramatyka bezkontekstowa jest jednoznaczna, to nie występuje w niej lewostronna rakuręja.

Determlnlsacja automatu skończonego moitł spowodować wykładniczą eksplozję liczby stanów.

Automat stosowy w każdym kroku wczytuj n dokładnie Jeden znak.

Żeton ruprestmtnje parę: teksem, atrybut.

W pnrsornch LI(1) drzewo wyprowadzenia Jest odtwarzane od korzenia do liści. Parsery LR(1) obchodzą drzewo wyprowadzenia w porządku prefiksowym. Anollsator składniowy generowany przez Yn<'c'a/niBon'a to rodzaj deterministycznego automatu stosowego.

Konstrukcja parsem ŁR(ł) nie może się udać dla gramatyki niejednoznacznej. Yttęe l Tilaon Implementują mechanizm atrybutów dziedziczonych.

td

<?

v

i

W