DSC00944 3

Nr indeksu;

Teoretyczne podstawy informatyki - egzamin Nazwisko i imię:

Zadanie l._ Przekształć podaną gramatykę (reguły produkcji), aby była monotootean* i posaiafa jafi najmniejszą liczbę reguł.

Język L generowany jest za pomocą gramatyki G = <{S AB 0,1}, {0,1}, P. S>o nas*ęniiąrvK aSwaae s-sae produkcjiP: S->0a|ibIa, OA->OB|ll|o, B-*0S|bi|1

Czy podany język L(G) jest:_Uwaga! l easadak kartą

(a)    regularny

(b)    bezkontekstowy

(c)    kontekstowy

(d)    rekurencyjnie przeliczalny

Zadanie 3. Automat Moore’a podany jest w tabeli.

Stan	a	b	c	j Wy
1	2	1	2	X
2	2	1	3 | Y
3	3	2	2	Z

A)    Napisz układ równań, z którego można wyzaacrję R®

B)    Wyznacz R31.