Иерархия Хомского формальных грамматик — различия между версиями
Leugenea (обсуждение | вклад) м (→Класс 2) |
Leugenea (обсуждение | вклад) м (Доубирал нелепое слово «те») |
||
| Строка 11: | Строка 11: | ||
|id = Неукорачивающие грамматики | |id = Неукорачивающие грамматики | ||
|definition = | |definition = | ||
| − | '''Неукорачивающие грамматики''' — это | + | '''Неукорачивающие грамматики''' — это формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha|\leq|\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).}} |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''Контекстно-зависимые грамматики''' — это | + | '''Контекстно-зависимые грамматики''' — это формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha A \beta\rightarrow\alpha\gamma\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{*}</tex>, <tex>A \in N</tex> и <tex>\gamma \in \{\Sigma\cup N\}^{+}</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).}} |
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]], неукорачивающие грамматики эквивалентны контекстно-зависимым. | Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]], неукорачивающие грамматики эквивалентны контекстно-зависимым. | ||
| Строка 29: | Строка 29: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
| − | '''Праволинейные (автоматные) грамматики''' — это | + | '''Праволинейные (автоматные) грамматики''' — это формальные грамматики, всякое правило из <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>.}} |
== Распознавание == | == Распознавание == | ||
Версия 06:34, 23 января 2012
| Определение: |
| Иерархия Хомского — классификация формальных грамматик и задаваемых ими языков, согласно которой они делятся на 4 класса по их условной сложности. |
Содержание
Класс 0
К нулевому классу относятся все формальные грамматики. Элементы этого класса называются неограниченными грамматиками, поскольку на них не накладывается никаких ограничений. Практического применения в силу своей сложности такие грамматики не имеют.
Класс 1
Первый класс представлен неукорачивающими и контекстно-зависимыми грамматиками.
| Определение: |
| Неукорачивающие грамматики — это формальные грамматики, всякое правило из которых имеет вид , где и (возможно правило , но тогда не встречается в правых частях правил). |
| Определение: |
| Контекстно-зависимые грамматики — это формальные грамматики, всякое правило из которых имеет вид , где , и (возможно правило , но тогда не встречается в правых частях правил). |
Как будет показано далее, неукорачивающие грамматики эквивалентны контекстно-зависимым.
Класс 2
Второй класс составляют контекстно-свободные грамматики.
| Определение: |
| Контекстно-свободные грамматики — это формальные грамматики, всякое правило из которых имеет вид , где , . |
Класс 3
Элементами третьего класса являются праволинейные (автоматные) грамматики.
| Определение: |
| Праволинейные (автоматные) грамматики — это формальные грамматики, всякое правило из которых имеет вид либо , где ,, . |
Распознавание
Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица сопоставляет классы иерархии Хомского, языки, которые ими задаются, и машины, которые распознают эти языки.
| Грамматика | Языки | Машина |
|---|---|---|
| Класс 0 | рекурсивно перечислимые | машина Тьюринга |
| Класс 1 | контекстно-зависимые | ЛПА |
| Класс 2 | контекстно-свободные | автоматы с магазинной памятью |
| Класс 3 | регулярные | конечные автоматы |
Источники
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. - Т. 1,2.
