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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Класс 1)
(Класс 1)
Строка 14: Строка 14:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Контекстно-зависимые грамматики''' - это те формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>\alpha A \beta\rightarrow\alpha\gamma\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{*}</tex> и <tex>\gamma \in \{\Sigma\cup N\}^{+}</tex>(возможно правило <tex>$S$  \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).}}
+
'''Контекстно-зависимые грамматики''' - это те формальные грамматики, всякое правило из <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> не встречается в правых частях правил).}}
  
 
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]] неукорачивающие грамматики эквивалентны контекстно зависимым.
 
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]] неукорачивающие грамматики эквивалентны контекстно зависимым.

Версия 07:41, 3 ноября 2011

Определение:
Иерархия Хомского — классификация формальных грамматик и задаваемых ими языков, согласно которой они делятся на 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

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