Изменения

'''Праволинейные(автоматные) грамматики''' - это те формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>A \rightarrow tB</tex> либо <tex>A \rightarrow t</tex>, где <tex>A\in N</tex>,<tex>B\in N</tex>, <tex>t\in \Sigma </tex>.}}

Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица обощает классы иерархии Хомского, языки, которые ими задаются, и машины, которые распознают эти языки.

{| class="wikitable"

| Класс 1

| контектно-зависимые

|-

| Класс 2

| [[Детерминированные конечные автоматы|конечные автоматы]]

|}