index předchozí 1 2 3 4 5 6 7 8 9 10 11 12 následující

Cvičení desáté

Vztah TS a gramatik typu 0, uzávěrové vlastnosti

1) Je daný DTS T (resp. jeho část). Podle algoritmu ze skript navrhněte k němu
ekvivalentní gramatiku:

	d(q,) = (q,,R)	d(q,a) = (p,A,R)
	d(p,b) = (q,a,L)	d(q,_) = (p,A,R)
	d(p,_) = (q,a,L)	d(q,a) = (q_accept,A,R)

Kde * je značka pro levý konec pásky, stavy jsou {p,q,q_accept}
vstupní abeceda {a,b} a pásková abeceda {*,A,a,b}.

2) O každé z následujících implikací rozhodněte zda je pravdivá

R je regulární, L je rek. spočetný => R průnik L je regulární
L je rekurzivní => co-L je rekurzivní
L je rekurzivní => L^* je rekurzivní (Zkuste neformální důkaz)
L je kontextový => co-L je rekurzivní (Zkuste neformální důkaz)

3) Navrhněte gramatiky pro následující jazyky:

{ w | w náleží {a,b,c}^*, #_a(w)=#_b(w)=#_c(w) }
{ ww | w náleží {a,b,c}^* }
{ aⁿbⁿcⁿ | n>=0 }
{ aⁿ | n je mocnina 2 }