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