Zásobníkový automat

z Wikipédie, slobodnej encyklopédie
Jump to navigation Jump to search
Zasobnikovy automat.png

Zásobníkový automat je názov pre triedu abstraktných matematických strojov.

Zásobníkové automaty (ďalej len ZA) umožňujú reprezentovanie bezkontextových jazykov ich rozpoznávaním. Oproti konečným automatom sú rozšírené o špeciálny typ pamäte, zásobník. ZA M možno definovať ako usporiadanú sedmicu:

M=(Q, T, G, D, q0, Z0, F)

kde:

  • Q - konečná neprázdna množina stavov
  • T - konečná neprázdna množina vstupných symbolov - vstupná abeceda
  • G - konečná neprázdna množina zásobníkových symbolov - zásobníková abeceda
  • D - prechodová funkcia
  • q0 - začiatočný stav, patrí do množiny Q
  • Z0 - symbol na dne zásobníka, patrí G
  • F - konečná množina koncových (finálových) stavov

ZA disponuje vstupnou páskou, na ktorej sú symboly zo zásobníkovej abecedy, tie sú čítané zľava doprava čítacou hlavou. Tá sa môže posúvať vždy iba doprava o jeden symbol, čítanie symbolov sa však môže zastaviť. Symboly na vstupnej páske nemôže ZA meniť. Zásobník je potenciálne nekonečná pamäť s prístupom LIFO (Last In First Out). ZA je v určitom stave, ktorý je popísaný neprečítanou časťou pásky, stavom, v ktorom sa nachádza riadiaca jednotka ZA a obsahom zásobníka. ZA je matematickým modelom vykonávajúcim syntaktickú analýzu metódou zhora nadol, derivačný strom sa konštruuje od koreňa k listom a vykonáva sa ľavý rozklad analyzovanej vety.

ZA môžu byť v zásade dvojakého typu:

  • Deterministické
  • Nedeterministické

Vo všeobecnosti je ZA nedeterministický, pri prechode ZA z jedného stavu do iného nemusí byť jasné:

  • do akého stavu má ZA prejsť a akým reťazcom má byť prepísaný symbol z vrcholu zásobníka
  • či čítať ďalší vstup z pásky alebo nie

Nedeterministický ZA možno determinizovať, neplatí však, že ku každému nedeterministickému ZA existuje deterministický ZA. Platí, že ku každej bezkontextovej gramatike G =(N, T, P, S) existuje nedeterministický ZA M taký, že L(M)=G(M).

K obrázku:

  • VP - vstupná páska
  • KRJ - Konečnostavová riadiaca jednotka
  • H - Čítacia hlava
  • Z - Zásobník
Formálne jazyky, automaty a gramatiky
Chomského
hierarchia
Gramatiky Jazyky Minimálny
automat
Typ-0 Frázová Rekurzívne vyčísliteľný Turingov stroj
Rekurzívny Vždy zastavujúci Turingov stroj
Typ-1 Kontextová Kontextový (Nedeterministický) lineárne ohraničený
Typ-2 Bezkontextová Bezkontextový (Nedeterministický) zásobníkový
Typ-3 Regulárna Regulárny Konečný
Každá množina jazykov alebo gramatík je vlastnou nadmnožinou množiny priamo pod ňou.