Maszyna Turinga

[Who knew]

Witam, proszę o pomoc, nie rozumiem co mam zrobic w tym zadaniu

Dany jest alfabet s={x,y,z} oraz zbiór stanów G={g0, g1, g2, g3} gdzie g0 to stan początkowy a g3 to stan końcowy a w tym stanie znajduje się zapis xxyxy. Sprawdzić czy maszyna Turinga o tablicy chara przeczyta wszystko.

g0 g1 g2 g3
X g1p g1p g2p g3p
Y g1p g2p g3p g3p
Z g0p g3p g1p g3p

[cienisty]

Stan Symbol Formuła
g0 x (x, g1, ->)
g1 x (x, g1, ->)
g1 y (y, g2, ->)
g2 x (x, g2, ->)
g2 y (y, g3, ->)

Wniosek: maszyna nie trafiła przed końcem napisu na stan g3, więc przeczyta wszystko