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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Иерархия Хомского''' — классификация [[формальных языков]] и [[формальных грамматик]], согласно которой они делятся на 4 класса по их условной сложности.
+
'''Иерархия Хомского''' — классификация [[формальные языки|формальных языков]] и [[формальные грамматики|формальных грамматик]], согласно которой они делятся на 4 класса по их условной сложности.
 
}}
 
}}
 
== Класс 0 ==
 
== Класс 0 ==

Версия 07:46, 8 декабря 2010

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

Класс 0

К нулевому классу Хомского относятся грамматики [math] \Gamma = \langle\Sigma, N, S \in N,P\subset N^{*}\times (\Sigma\cup N)^{*}\rangle[/math], на которые не накладывается никаких ограничений, кроме указанных в определении понятия формальные грамматики.

Класс 1

Класс 1 представлен неукорачивающими грамматиками.

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

Класс 2

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

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

Класс 3

Класс 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].