Zásobníkový automat

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.

K obrázku:

• VP - vstupná páska
• KRJ - Konečnostavová riadiaca jednotka
• H - Čítacia hlava
• Z - Zásobník

Súbor:Zasobnikovy automat.gif