Шаблон:Формални језици и граматике

Хијерархија Чомског	Граматике	Језици	Апстрактне машине
Тип-0 — Тип-1 — — — — — Тип-2 — — Тип-3 — —	Без ограничења (без уобичајеног имена) Контекст сензитивна Positive range concatenation Индексирана — Linear context-free rewriting systems Tree-adjoining Контекст-слободна Детерминистичка контекст-слободна Visibly pushdown Регуларна — Non-recursive	Рекурзивно пребројиви Рекурзивни Контекст сензитивни Positive range concatenation^* Индексиран^* — Linear context-free rewriting language Tree-adjoining Контекст-слободни Детерминистички контекст-слободни Visibly pushdown Регуларан Star-free Финитни	Тјурингова машина Одлучивач Линеарно-ограничени PTIME Тјурингова машина Угњеждени стек Thread automaton restricted Tree stack automaton Embedded pushdown Недетерминистички потисни Детерминистички потисни Visibly pushdown Коначни Counter-free (with aperiodic finite monoid) Acyclic finite

Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.