Иерархия Хомского формальных грамматик — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Класс 1)
(Распознавание)
Строка 32: Строка 32:
  
 
== Распознавание ==
 
== Распознавание ==
Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица обобщает классы иерархии Хомского, языки, которые ими задаются, и машины, которые распознают эти языки.
+
Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица сопоставляет классы иерархии Хомского, языки, которые ими задаются, и машины, которые распознают эти языки.
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-

Версия 21:12, 22 января 2012

Определение:
Иерархия Хомского — классификация формальных грамматик и задаваемых ими языков, согласно которой они делятся на 4 класса по их условной сложности.

Класс 0

К нулевому классу относятся все формальные грамматики. Элементы этого класса называются неограниченными грамматиками, поскольку на них не накладывается никаких ограничений. Практического применения в силу своей сложности такие грамматики не имеют.

Класс 1

Первый класс представлен неукорачивающими и контекстно-зависимыми грамматиками.

Определение:
Неукорачивающие грамматики — это те формальные грамматики, всякое правило из [math]P[/math] которых имеет вид [math]\alpha\rightarrow\beta[/math], где [math]\alpha , \beta \in \{\Sigma\cup N\}^{+}[/math] и [math]|\alpha|\leq|\beta|[/math] (возможно правило [math]$S$ \to \varepsilon[/math], но тогда [math]$S$[/math] не встречается в правых частях правил).


Определение:
Контекстно-зависимые грамматики — это те формальные грамматики, всякое правило из [math]P[/math] которых имеет вид [math]\alpha A \beta\rightarrow\alpha\gamma\beta[/math], где [math]\alpha , \beta \in \{\Sigma\cup N\}^{*}[/math], [math]A \in N[/math] и [math]\gamma \in \{\Sigma\cup N\}^{+}[/math] (возможно правило [math]$S$ \to \varepsilon[/math], но тогда [math]$S$[/math] не встречается в правых частях правил).


Как будет показано далее, неукорачивающие грамматики эквивалентны контекстно-зависимым.

Класс 2

Второй класс составляют контекстно-свободные грамматики.

Определение:
Контекстно-свободные грамматики — это те формальные грамматики, всякое правило из [math]P[/math] которых имеет вид [math]A \rightarrow\beta[/math], где [math]A\in N [/math], [math]\beta \in \{\Sigma \cup N\}^{+}[/math].


Класс 3

Элементами третьего класса являются праволинейные (автоматные) грамматики.

Определение:
Праволинейные (автоматные) грамматики — это те формальные грамматики, всякое правило из [math]P[/math] которых имеет вид [math]A \rightarrow tB[/math] либо [math]A \rightarrow t[/math], где [math]A\in N[/math],[math]B\in N[/math], [math]t\in \Sigma [/math].


Распознавание

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

Грамматика Языки Машина
Класс 0 рекурсивно перечислимые машина Тьюринга
Класс 1 контекстно-зависимые ЛПА
Класс 2 контекстно-свободные автоматы с магазинной памятью
Класс 3 регулярные конечные автоматы

Источники

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. - Т. 1,2.