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

z Wikipédie, slobodnej encyklopédie
Smazaný obsah Přidaný obsah
Madoš (diskusia | príspevky)
Bez shrnutí editace
Madoš (diskusia | príspevky)
Bez shrnutí editace
Riadok 16: Riadok 16:


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.
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.

[[Obrázok:zasobnikovy_automat.gif|right|thumbnail|]]

Verzia z 16:25, 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.

Súbor:Zasobnikovy automat.gif