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

Smazaný obsah Přidaný obsah

V textu

Verzia z 18:48, 1. február 2005

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

@@ Riadok 2: / Riadok 2: @@
 '''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.
+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:
@@ Riadok 15: / Riadok 15: @@
 *'''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
+*'''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 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:
@@ Riadok 28: / Riadok 28: @@
 *č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).
+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: