Prijeđi na sadržaj

Automat s ugniježđenim stogom

Izvor: Wikipedija

U teoriji automata, automat s ugniježđenim stogom je konačni automat koji može koristiti podatkovnu strukturu potisni stog koja sadrži podatke koji mogu biti dodatni stogovi. Automat s ugniježđenim stogom, pored uzimanja i dodavanja elemenata sa stoga, može i čitati sadržaj stoga. Automat s ugniježđenim stogom prepoznaje klasu indeksiranih jezika.

Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.


Nedovršeni članak Automat s ugniježđenim stogom koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.