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