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

Odobraných 8 bajtov ,  pred 17 rokmi
d
chýba zhrnutie úprav
Bez shrnutí editace
dBez shrnutí editace
'''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:
 
*'''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:
*č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:
15 630

úprav