Automaty ze stosem

Automaty ze stosem

Pomocny jest tu bardziej skomplikowany automat, tzw. automat ze stosem czyli pamięcią zorganizowana w stos nakładających się informacji (stos kartek z informację). Najniższa informacja (na dole)mówi, że stos jest pusty. Najwyższa jest aktualna. Można ia zmienić dokładając nowa lub zdejmując aktualna. W ten tylko sposób można dotrzeć do wnętrza stosu (czyli przez zdejmowanie).

Definicja automatu ze stosem A z S jest to siódemka Az S = (Q,T, Z, P, z, q, F) gdzie Q, T, P, F jak przedtem, zaś Z to alfabet, którym posługujemy się na stosie, a z symbol na samym dnie stosu.

Teraz P:TxQxZ=?-QxZ, zaś P(r, a, t) (p, $) oznacza, że będąc w stanie r, czytając a z wejścia i widząc ? na stosie, automat przechodzi do stanu p i kładzie na stosie $ zamiast t.

Przykład:

Prześledźmy działanie tego automatu ze stosem na przykładzie języka aⁿbⁿ. P(q, a, z) =*• (p, az), P(p, a, az) =*• (p, aaz), P(p, b, aaz) =*• (r, az), P(r, b, az) =* (r, z)

Zobaczymy jak przebiega akceptacja słowa aabb

(q, aabb, z) =* (p, abb, az) =» (p, bb, aaz) =*• (r, b, az) =*• (r, @z)

czyli aabb jest akceptowane przez A z S.

A z S odpowiada gramatykom bezkontekstowym, czyli dla dowolnej gramatyki bezkontekstowej można zbudować automat ze stosem, który akceptuje język generowany przez nią.

Istnieją jednak języki (np. aⁿbⁿcⁿ — kontekstowy), dla których nie da się zbudować automatu ze stosem. Można dla niego zbudować nowy automat tzw. MT (od nazwy "maszyna Turinga"— modelem maszyny Turinga będziemy się zajmować pod koniec tego kursu).