418
правок
Изменения
Нет описания правки
{{Определение
|definition=
'''Иерархия Хомского''' (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
}}
== Класс 0 ==
===Пример===
Терминалы: <tex>\Sigma = \{a, c, d\};</tex>
Нетерминалы: <tex>N = \{S, A, B\};</tex>
Продукции:
|id = Неукорачивающие грамматики
|definition =
'''Неукорачивающая грамматика''' (англ. ''noncontracting grammar'') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>\alpha\rightarrow\beta</tex>, где <tex>\alpha , \beta \in \{\Sigma\cup N\}^{+}</tex> и <tex>|\alpha|\leqleqslant |\beta|</tex> (возможно правило <tex>S \rightarrow \varepsilon</tex>, но тогда <tex>S</tex> не встречается в правых частях правил).
}}
===Пример===
Язык <tex>L=\{w \in \Sigma^* | w = 0^n1^n2^n, n \ge geqslant 1\}</tex>
Терминалы: <tex>\Sigma = \{0, 1, 2\}</tex>;
Нетерминалы: <tex>N = \{S, A\}</tex>;
Продукции:
Язык <tex>L=\{w \in \Sigma^* | w = w^R\}</tex> (язык палиндромов).
Терминалы: буквы алфавита <tex>\Sigma</tex>;
Нетерминалы: <tex>N = {S}</tex>;
Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>;
Язык <tex>L</tex> для регулярного выражения <tex>a^*bc^*</tex>.
Терминалы: <tex>\Sigma = \{a, b, c\};</tex>
Нетерминалы: <tex>\{S, A\};</tex>
Продукции:
