Аутомат са угњежденим стеком
Из Википедије, слободне енциклопедије
У теорији аутомата, аутомат са угнежђеним стеком је коначни аутомат који може да користи стек који садржи податке који могу да буду додатни стекови.[1] Аутомат са угњежедним стеком може да чита свој стек осим што може да врши класичне операције уметања на стек и скидања са стека. Аутомат са угнежђеним стеком је у стању да препозна индексиран језик.[2]
Види још [уреди]
Извори [уреди]
- ^ Aho, Alfred (1969). „Nested stack automata“. Journal of the ACM 16 (3): 383–406. DOI:10.1145/321526.321529. ISSN 0004-5411.
- ^ 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 | Регуларна | Регуларан | Коначни |
| Свака категорија језика или граматика је прави подскуп категорије директно изнад ње. | |||
