Zásobníkový automat: Rozdiel medzi revíziami

z Wikipédie, slobodnej encyklopédie
Smazaný obsah Přidaný obsah
TXiKiBoT (diskusia | príspevky)
TXiKiBoT (diskusia | príspevky)
d robot Pridal: sh:Potisni automat
Riadok 54: Riadok 54:
[[pt:Autômato de pilha]]
[[pt:Autômato de pilha]]
[[ru:Автомат с магазинной памятью]]
[[ru:Автомат с магазинной памятью]]
[[sh:Potisni automat]]
[[sr:Потисни аутомат]]
[[sr:Потисни аутомат]]
[[zh:下推自动机]]
[[zh:下推自动机]]

Verzia z 21:53, 4. august 2009

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