Изменения

Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица обощает классы иерархии Хомского, языки, которые ими задаются, и автоматымашины, которые распознают эти языки.{| class="wikitable"|-! Грамматика! Языки! Машина|-| Класс 0| [[ Перечислимые языки | рекурсивно перечислимые ]]| [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 машина Тьюринга]|-| Класс 1| контектно-зависимые| [http://en.wikipedia.org/wiki/Linear_bounded_automaton | ЛПА]|-| Класс 2| контекстно-свободные| [[Автоматы с магазинной памятью|автоматы с магазинной памятью]]|-| Класс 3| [[Регулярные языки: два определения и их эквивалентность|регулярные]]| [[Детерминированные конечные автоматы|конечные автоматы]]|}