Аутомат са угњежденим стеком

Из Википедије, слободне енциклопедије

У теорији аутомата, аутомат са угнежђеним стеком је коначни аутомат који може да користи стек који садржи податке који могу да буду додатни стекови.[1] Аутомат са угњежедним стеком може да чита свој стек осим што може да врши класичне операције уметања на стек и скидања са стека. Аутомат са угнежђеним стеком је у стању да препозна индексиран језик.[2]

Види још[уреди]


Референце[уреди]

  1. ^ Aho, Alfred (1969). „Nested stack automata“. Journal of the ACM 16 (3): 383–406. DOI:10.1145/321526.321529. ISSN 0004-5411. 
  2. ^ Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. стр. 536–542. ISBN 978-90-277-2245-4. 

Литература[уреди]

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.


  • Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. стр. 536–542. ISBN 978-90-277-2245-4.