dsc00103

o

y

Automaty i Gramatyki

rok

Imię i nazwisko:

Nr indeksu: .................32.^6,

.St

3

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

a)	gf
b)	((ab	} ba)’(aa | 66)*)*
c)	(a^4 |	A
d)	(o66a)*(aa66)‘
c)	(ab f	ba)'(aa | 66)*

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

b) lal 6	1 1 ((a 1 b)(a 1 6))*
-FI | 2 | 2
2 11

c)

łajb
-J	_LtL
	I f 2
	m i 6
— I J	^1,2
F2J	a | 6
-A	* <
*!	■ f V *

i>G2 2) Q] 3) [Tj 4) cg s) CD

	a	1*
— 11	»|	[1
F2

0

|u I 6.1*6    *)&

'ab)' 0

LdJ

³T«rTl Czy następująca gramatyka jwt jednoznaczna? S — aS Sb i t

1 T1 Cży w następującej gramatyce makr prowadzić puste słowo? S -* aS X -*bSa | e

S- | Tl Czy w następującej gramatycr mor na wy prowadzić słowo baba? S — aSb | bSa | t

''f tyl ^ 1 Czy język generowany przn następu.

jącą gramatykę jest skończony? 5 ••• aSb | bSa I c

"4- aj [ Ni | Czy następująca gramatyka generuje pu-sty język? S — SaS | bSb I a

4. I I Każdy język skończony Jest regularny.

| Determinizacja automatu skońrzoir może spowodować wykładniczą ckir liczby stanów.

n_ f I 'f j Żeby gramatyku liCz,kanU‘k.iióWn by noznaczna, to każde słowo musi mi niej co najwyżej Jedno wyprowadzenie.

L I I Gramatyki liniowe opisują Języki regularne.

#j! Nl Obliczenie automatu stosowego mods być nieskończone („zapętlać się"),

5. [    | Przecięcie języków bcziumtckstowyrli jest

językiem bezkontekstowym.

f- _r[~rl Sama języków reguiarnych jest Językiem regularnym.

| Jeśli języki zł i żł są częściowo obliczalne,

(o są obliczalne.

{ I Język STOP jest obliczalny.

[ Każdy język kontekstowy jest obliczalny

) Analizator składniowy generowany przez Yacca/Bisona to rodzaj wluUimowj maszyny Turinga.

[ Analizator leksykalny generowany przez JFJtoca to rodzaj automatu skończonego.

| Parsęty LR(1) obchodzą drzewo wyprowadzenia w porządku postfiksowym.

[" 1 W parseraeh ŁL(1) tablice sterujące sa-wierają akcje słaft i redtice

t*bj gramatyka była U.(l), to mmi być jednoznaczna.