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