Turingov stroj

[jillefsky]

Viete niekto Turingove stroje, ja si s tym moc neviem rady..

11)sestrojit TS X={a,b} L(TS)={w| |w|=2k}. co to je za jazyk v Chomskeho usporadani

[Dawe]

E jakožto epsilon

(q0,E)->(qf,E,+1)
(q0,a)->(q1,E,+1)
(q0,b)->(q1,E,+1)
(q1,a)->(q0,E,+1)
(q1,b)->(q0,E,+1)

qf koncový, q0 počáteční stav.
Nevím jestli je to dobře, ale snad ano. Dělá to to, že to přečte písmeno, skočí do q1, přečte písmeno a skočí zpět do q0, pokud není další písmeno a je v q0, skočí do qf, pokud není další písmeno a je v q1, slovo není přimuto. +1 znamená, že se pořád pohybuju dál, pořád dál čtu vstup jako u KA.
Je to regulární jazyk, regexp: ((a+b)(a+b))*