Skladovni avtomat

Iz MaFiRaWiki

Skladovni avtomat je naprava, katere del je končni avtomat, lahko pa še uporablja sklad za zapisovanje podatkov.

Definicija

Nedeterministični skladovni avtomat W definiramo kot sedmerico: W = (Q,Σ,Γ,δ,q0,Z0,F), kjer je

  • Q končna množica stanj
  • Σ končna vhodna abeceda
  • Γ končna skladovna abeceda
  • \delta: Q \times ( \Sigma \cup \left \{ \epsilon \right \} ) \times \Gamma \to P( Q \times \Gamma ^{*}) prehodna funkcija
  • q_0\in Q začetno stanje
  • Z_0\in\Gamma začetni skladovni simbol
  • F \subset Q množica končnih stanj.

Delovanje

Skladovni avtomat se razlikuje od navadnega končnega avtomata v dveh stvareh:

  1. Lahko uporabi vrh sklada, da izbere naslednje stanje.
  2. Lahko manipulira s skladom kot delom prehoda med stanji.

Skladovni avtomat ima vhodni trak, ki ga beremo od leve proti desni (nanj pa ne moremo pisati), in na katerem je zapisana vhodna beseda. Ima tudi sklad, ki je trak, ki omogoča dostop le do svojega zadnjega elementa (na vsakem koraku ga lahko preberemo in izbrišemo ali pa nov element dodamo za predhodnim). Ta element imenujemo vrh sklada. Pri skladovnem avtomatu obstaja tudi nadzorna enota, ki vsebuje notranja stanja Q, deluje pa takole: če je trenutno stanje q, trenutni vhodni simbol a, vrh sklada Z in če obstaja element δ, ki je enak \langle\langle q, a,Z\rangle, \langle r, \gamma\rangle\rangle, je naslednje stanje r, bralno okno se premakne za en simbol proti desni, vrh sklada Z pa se zamenja z besedo γ. Drugi možni korak ustreza elementom δ oblike \langle\langle q, \epsilon,Z\rangle, \langle r, \gamma\rangle\rangle. V tem primeru korak ni odvisen od vhodnega simbola in čitalno okno se ne premakne.

Če je končni avtomat nedeterminističen, dobimo nendeterminističen skladovni avtomat (NSA). Če uporabimo deterministični končni avtomat, je rezultat deterministični skladovni avtomat (DSA), ki je šibkejši.

Če namesto enega sklada uporabimo dva, dobimo Turingov stroj, ki je še močnejši.

Jeziki, ki jih razpoznavajo skladovni avtomati, so natanko kontekstno neodvisni jeziki.

Zgled

Kontekstno-neodvisen jezik \{a^kb^k | k \ge 0 \} lahko razpozna naslednji skladovni avtomat:

M = (\{q_0, q_1, q_2, q_3\}, \{a,b\}, \{A,\underline{A}\}, \delta, q_0, \{q_0, q_3\} ),

kjer so prehodi

\delta(q_0, a, \epsilon) = \{(q_1, \underline{A})\}

δ(q1,a,ε) = {(q1,A)}

δ(q1,b,A) = {(q2,ε)}

\delta(q_1, b, \underline{A}) = \{(q_3, \epsilon)\}

δ(q2,b,A) = {(q2,ε)}

\delta(q_2, b, \underline{A}) = \{(q_3, \epsilon)\}

\delta(q, \theta, \rho) = \empty za ostale (q,θ,ρ)


Pomen prehodov lahko pojasnimo tudi z opazovanjem prvega prehoda

\delta(q_0, a, \epsilon) = \{(q_1, \underline{A})\}

Ko je trenutno stanje q0, a vhodns črka in ε na vrhu sklada, gre avtomat v stanje q1 in se na vrh sklada zapiše \underline{A}.

Image:automateapile.png

Osebna orodja