Изменения

'''Иерархия Хомского''' — (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.

'''Неукорачивающие грамматикиНеукорачивающая грамматика''' — (англ. ''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$ \to rightarrow \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).

'''Контекстно-зависимые грамматикизависимая грамматика''' — (англ. ''context-sensitive grammar'') {{---}} это формальные грамматикиформальная грамматика, всякое правило из <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 rightarrow \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).

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

== Класс 2 =Пример===Второй класс составляют [[Контекстно-свободные грамматики<tex>L=\{w \in \Sigma^* \mid w = 0^n1^n2^n, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]].n \geqslant 1\}</tex> Продукции:

Type-2 grammars (context-free grammars) generate the context-free languages. These are defined by rules of the form A <tex>S \rightarrow 012 \gamma with A a nonterminal and \gamma a string of terminals andS \rightarrow 0AS2 \\A0 \rightarrow 0A \\ A1 \rightarrow 11 </or nonterminals. These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton. Context-free languages – or rather the subset of deterministic context-free language – are the theoretical basis for the phrase structure of most programming languages, though their syntax also includes context-sensitive name resolution due to declarations and scope. Often a subset of grammars are used to make parsing easier, such as by an LL parser.tex>

'''Контекстно-свободные грамматикисвободная грамматика''' — (англ. ''context-free grammar'') {{---}} это формальные грамматикиформальная грамматика, всякое правило из <tex>P</tex> которых которой имеет вид <tex>A \rightarrow\beta</tex>, где <tex>A\in N </tex>, <tex>\beta \in \{\Sigma \cup N\}^{+}</tex>.

Элементами третьего К третьему типу относятся '''автоматные''' или '''регулярные грамматики''' (англ. ''regular grammars'') {{---}} самые простые из формальных грамматик, которые задают [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярные языки]]. Они являются контекстно-свободными, но с ограниченными возможностями. Все регулярные грамматики могут быть разделены на два эквивалентных класса являются следующего вида:{{Определение|definition ='''Леволинейная грамматика'''праволинейные (автоматныеангл. ''left-regular grammar''){{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>A \rightarrow B\gamma</tex> или <tex>A \rightarrow \gamma</tex>, где <tex>\gamma \in \Sigma, A, B \in N</tex>.}}{{Определение|definition ='''Праволинейная грамматика''' (англ. ''right-regular grammar' грамматики') {{---}} это формальная грамматика, всякое правило из <tex>P</tex> которой имеет вид <tex>A \rightarrow \gamma B</tex>; или <tex>A \rightarrow \gamma</tex>, где <tex>\gamma \in \Sigma, A, B \in N</tex>.}}Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык уже не обязан быть регулярным.

К третьему типу относятся Также можно [[регулярные грамматикиПравоконтекстные_грамматики,_эквивалентность_автоматам|показать]] (автоматные) — самые простые из формальных грамматик. Они являются контекстно-свободными, но с ограниченными возможностямичто множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых [[Детерминированные конечные автоматы|конечными автоматами]].

Все регулярные грамматики могут быть разделены на два эквивалентных класса, которые для грамматики вида III будут иметь правила следующего вида:===Пример===* <tex>A \rightarrow B\gammaL</tex> или <tex>A \rightarrow \gammaдля регулярного выражения </tex>, где <tex>\gamma \in V_Ta^*, A, B \in V_N</tex> (для леволинейных грамматик).* <tex>A \rightarrow \gamma B</tex>; или <tex>A \rightarrow \gamma</tex>, где <tex>\gamma \in V_Tbc^*, A, B \in V_N</tex> (для праволинейных грамматик).Регулярные грамматики применяются для описания простейших конструкций: [[идентификатор]]ов, [[Строковый тип|строк]], [[Константа (программирование)|констант]], а также [[язык ассемблера|языков ассемблера]], [[командный процессор|командных процессоров]] и др.

{{Определение|definition ='''Праволинейные (автоматные) грамматики''' — это формальные грамматики, всякое правило из <tex>P</tex> которых имеет вид <tex>A S \rightarrow tB</tex> либо <tex>aS\ |\ bA \\A \rightarrow t</tex>, где <tex>A\in N</tex>,<tex>Bvarepsilon\in N</tex>, <tex>t|\in \Sigma cA</tex>.}}

== Распознавание См. также ==Для языков, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознают. Следующая таблица сопоставляет классы иерархии Хомского, языки, которые ими задаются, и машины, которые распознают эти языки.{| class="wikitable"|-! Грамматика! Языки! Машина|-| Класс 0| * [[ Перечислимые языки | рекурсивно перечислимые ]]| [http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 машина Тьюринга]|-| Класс 1| контекстно-зависимые| [http://en.wikipedia.org/wiki/Linear_bounded_automaton ЛПА]|-| Класс 2| контекстно-свободные| [[Автоматы с магазинной памятью|автоматы с магазинной памятью]]|-| Класс 3| [[Регулярные языки: два определения и их Правоконтекстные грамматики, эквивалентность|регулярныеавтоматам]]| * [[Детерминированные конечные автоматыВозможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|конечные автоматыВозможность порождения формальной грамматикой произвольного перечислимого языка]]|}