Automaty MT

Automaty MT

Automat taki dysponuje zbiorem wejściowym tzw. tasiemką wejściową, urządzeniem sterującym oraz tasiemką roboczą, na której obserwujemy jeden dowolny symbol, i która może przesuwać się w lewo, w prawo lub pozostać nieruchoma zmieniając obserwowany symbol na inny.

Formalnie MI to szóstka symboli: MT = (Q,T, Z, R, q, F) gdzie Q, T, Z, q, F mają znaczenie jak w A z S, z tym że zbiór Z zawiera dodatkowo znak pusty # występujący na końcach tasiemki roboczej lub wejściowej (po zapisanym słowie), R jest odpowiednikiem funkcji przejść zwanym lista rozkazów o postaci: (p, X, A) -» (r, B, ruch), (X — nieprzeczytana część słowa wejściowego), co rozumiemy: urządzenie zmienia stan z p na r, na tasiemce roboczej A zamienione jest w B, po czym tasiemka przesuwa się zgodnie z opisem "ruchu".

Konfiguracja MT zapisana jako (p, w, s ^A t) oznacza, że p jest aktualnym słowem w nieprzeczytaną częścią słowa wejściowego, zaś s i Mo zawartość tasiemki roboczej, przy czym obserwujemy pierwszy symbol słowa f. ^A oznacza, że jesteśmy przed t.

kreślmy zbiory występujące w MT:

Q = {q, P, r, s}

T = {a, b, c}

2 = {a, b, #}, ej jest stanem początkowym, zaś s końcowym.

przy czym Z — to co można zapisać na tasiemce roboczej(odpowiednik alfabetu stanu)

P czyli zbiór rozkazów to:

(q, a. #) -> (q. a, lewo) I (q, b, #) -» (p, b, prawo) II (p, b, a) -» (p, b, prawo) III (p, c, a) —> (r, #, lewo) IV (r, c, b) -»(r, #, lewo) V (r, @, b)-» (s,#, stój) VI

Rozważmy akceptację słowa aabbc € aⁿb^r,cⁿ

	wczytano a wpisano a na	wpis a i
rozkaz	tas. roboczej i przesunięto w lewo	przesunięto w lewo	jeśli jesteśmy
(q, aabbcc, #)	=* (q, abbcc, a ^A #) =*	(q, bbcc, aa ^A#)	przed końcem ti zatrzymujemy znak pusty

(p, bcc, a ^A ab)

opuszczono znak końca bo nie jesteśmy przed końcem

zastąpiono a przed b i przesunięto taśmę w prawo

b zastąpiono przez #

(opuszczono drugi #j i przesunięto taśmę w lewno

koniec

(stop)

(p,cc^Aabb) =4-    (r, c,#^Abb) =*•    (r, @,#^Ab)

Zatem aabbcc jest akceptowane przez automat MT, który akceptuje języki kontekstowe. Widać, że nie każdy automat może realizować dowolny algorytm. MT jako automat z nieskończenie duża namiecia. w której zawarta jest informacja o działaniu algorytmu (programu) może realizować każdy algorytm!