formální jazyky a automaty i CVIČENI 10
1. Použitím algoritmu z přednášky zkonstruujte gramatiku G, generující jazyk, který je akcep-
tovaný Turingovym strojem M, kde M = {{g,h,h0,k,l,f}, {a,b}, {a,b,M,N,N0, B} ô, h0, {f}), 5:   5(h0,a) ={(g,N0,R)}
5(h, a)     ={(g,N,0),(h,a,R), (h,a,L)}
5(g,b)     = {(h,M,0),(g,b,R),(g,b,L)}
6(h, x)     = {{h,x, R), (h,x, L)} x£{b,N,M}
S(g, y)   = ífe.y.R). fe.y. L)> y e {«,n,m}
5(h,N0) ={(k,N0,R)}
ô(k,N) ={(k,N,R)}
ô(k,M) ={(l,M,R)}
5(1, M) ={(l,M,R)}
5(1, B) = {(f,N0,O)}
2. Rozhodněte, jestli třída jazyků akceptovaných Turingovymi stroji je uzavřena vzhledem k ope-
raci kvocientu s regulárními jazyky, tzn. jestli pro libovolný jazyk M (nad abecedou T,m, akceptovaný nějakým Turingovym strojem M) a jazyk R (nad abecedou T,r, akceptovaný nějakým konečným automatem 7?.) je možné zkonstruovat Turingův stroj £ akceptující jazyk L = {x £ T,*M | 3y £ R : xy £ M}.
1