5638684949

Wk

Mm#

Języki Formalne i Automaty Egzmnin 2011/2012

4.

jpłia^U¹ £gjj£Z -j^j^jUłe wzorce Oti Jtftj-

iZgjjgo V	w sensie	: zawjei arna
	d)
irtfU’	ą	4t Jj6
\$jm?

M&MM0 dP tywstw 99tlących

J Czy    w    następującej    gramatyce

można wyprowadzić słowo aabb?

5 -+ a56 | 65a ] 6a

| Czy    w    następującej    gramatyce

można wyprowadzić puste słowo?

5 —> 5X | aXo, X —► o6| 6a J e Czy    następująca    gramatyka

generuje pusty język?

5 -> £S | 65 | a5

Czy język generowany przez następującą gramatykę jest skończony?

5 4 XXX l XaX | 6X6, X 6a6 | a6a | ba Czy    następująca    grama

tyka. jest jednoznaczna?

5 -» 55 | 65a | a6

Sklejenie języków regularnych jest językiem regularnym.

Każdy język regularny jest skończony.

Każdy język bezkontekstowy jest obliczalny. Gramatyki liniowe opisują języki regularne. Język STOP jest częściowo obliczalny.

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

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

"~"~] Żeby gramatyka bezkontekstowa była jednoznaczna, to każde 6łowo musi mieć w niej co najwyżej jedno drzewo wyprowadzenia.

~~~| Tablica konstruowana w algorytmie CYK zawiera liczby całkowite.

j Yacc/Bison służy do tworzenia analizatorów leksykalnych (skanerów).

Zaznacz do jakich klas należą podane języki:

a)    {a^łó^J c¹'’^ : j < i}

b)    {M : M nie akceptuje żadnego słowa}

c)    {aWć³ : i,j > 0}

d)    {a‘6⁷⁰”* : i < 50}

e)    {M : M akceptuje jakiekolwiek słowo}

Klasa    \ a)

j. regularne

j. bezkontekstowe, ale nie regularne j. obliczalne, ale nie bezkontekstowe j. częściowo obliczalne ale nie obliczalne

a

	4)	u	.1,6
ymmr.	??Slm		p
		i 3	jT
33KJ n_2* 1		P	pr
	. 4^2	a		1 □
awilar-.-			T
	IM	5l	jp|		■"""
	3	4	3		——
^Bł96^RSS13v4 ’’		T"	H		:
	Pr	gg	lf~ ■	>6.	23

^;:^Hr

!i j]

/pZŁ

l^-Jj (ti&i irfĄY

k___(J (i&fHłfril

/■ • [i (\£0fóflj l&jffjfyY'

3?    dtp :vdetfie -£fcW*<itykj ihęj^ntękstpwe i gęnerp-

	ii .5		|pgspgp|
	X		^ |§f
	5r"		W Y \ o.
			5#5 1 $>5 | s

ćf J5P

$

Spfl#

.. 1 ffilfatółWiyyn&d alfabetem -{a, 6} _j    aamp liter # i f»,

3    ńlUfił&i&pfifajj i# \igy$ąi nad alfabetem {a, 6},

jj    (ęffifgPtp■

j., które nie są częściowo obliczalne