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

Cvičení deváté

Konstrukce Turingových strojů

1) Navrhněte determinstický jednopáskový Turingův stroj rozhodující jazyk

L = {aⁿb^mcⁿd^m | m,n >=1 }

2) Navrhněte deterministický jednopáskový TS se vstupní abecedou {0,1} a takový, že výpočty na slovech tvaru 0^*1^* jsou akceptující a výpočty na ostatních slovech jsou nekonečné.

3) Navrhněte 3-páskový (vstupní + 2 pracovní pásky) TS pro jazyk

L = { w náleží {a,b}^* | #_a(w) = #_b(w)}

4) Navrhněte TS (determ. nebo nedeterm.) TS pro jazyk: (DÚ)

L = { aⁱb^jc^k | k = i*j }
L = { ww | w náleží {a,b}^* }
L = { a^p| p není prvočíslo }
L = { a_nw | w náleží {0,1}^*, w je binární zápis čísla n}