|
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:
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:
Vo všeobecnosti je ZA nedeterministický, pri prechode ZA z jedného stavu do iného nemusí byť jasné:
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:
|
||||||||||||||||||||||||||||||||
Portal di Ensiklopedia Dunia
