Изменения

Перейти к: навигация, поиск

Иерархия Хомского формальных грамматик

4414 байт добавлено, 12:39, 11 марта 2018
См. также
{{Определение
|definition=
'''Иерархия Хомского''' (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
}}
== Класс 0 ==
К нулевому классу относятся все [[Формальные_грамматики|формальные грамматики]]. Элементы этого класса называются '''неограниченные грамматикинеограниченными грамматиками''' (англ. ''unrestricted grammars''), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны [[Машина_Тьюринга|машиной Тьюринга]]. Эти языки также известны как '''[[Перечислимые_языки|рекурсивно перечислимые]]''' (англ. ''recursively enumerable'').  Правила можно записать в виде: <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha</tex> — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а <tex>\beta</tex> — любая цепочка символов из алфавита. Практического применения в силу своей сложности такие грамматики не имеют. ===Пример===Продукции: <tex>S \rightarrow aBcc \\B \rightarrow A \\BAA \rightarrow d \\Ac \rightarrow B \\A \rightarrow AAA\ |\ dB \\</tex> Выведем в данной грамматике строку <tex>addd</tex>: <tex>\boldsymbol{S} \Rightarrow a\boldsymbol{B}cc \Rightarrow a\boldsymbol{Ac}c \Rightarrow a\boldsymbol{B}c \Rightarrow a\boldsymbol{Ac} \Rightarrow a\boldsymbol{B} \Rightarrow a\boldsymbol{A} \Rightarrow ad\boldsymbol{B} \Rightarrow ad\boldsymbol{A} \Rightarrow ad\boldsymbol{A}AA \Rightarrow add\boldsymbol{BAA} \Rightarrow addd</tex>
== Класс 1 ==
Первый класс представлен '''неукорачивающими''' и '''контекстно-зависимыми''' грамматиками.
{{Определение
|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$ \to rightarrow \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).}} 
{{Определение
|definition =
'''Контекстно-зависимые грамматикизависимая грамматика''' (англ. ''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> не встречается в правых частях правил).}}Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.) [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|Известно]], что неукорачивающие грамматики эквивалентны контекстно-зависимым. ===Пример===<tex>L=\{w \in \Sigma^* \mid w = 0^n1^n2^n, n \geqslant 1\}</tex> Продукции:
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|далее]] неукорачивающие грамматики эквивалентны контекстно-зависимым.<tex>S \rightarrow 012 \\S \rightarrow 0AS2 \\A0 \rightarrow 0A \\ A1 \rightarrow 11 </tex>
== Класс 2 ==
Второй класс составляют [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]], которые задают контекстно-свободные языки. Эти языки распознаются с помощью [[Автоматы_с_магазинной_памятью|автоматов с магазинной памятью]].
{{Определение
|definition =
'''Контекстно-свободные грамматикисвободная грамматика''' (англ. ''context-free grammar'') {{---}} это те формальные грамматикиформальная грамматика, всякое правило из <tex>P</tex> которых которой имеет вид <tex>A \rightarrow\beta</tex>, где <tex>A\in N </tex>, <tex>\beta \in \{\Sigma \cup N\}^{+}</tex>.}}То есть грамматика допускает появление в левой части правила только одного нетерминального символа. ===Пример===<tex>L=\{w \in \Sigma^* \mid w = w^R\}</tex> (язык палиндромов). Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>
== Класс 3 ==
Элементами третьего класса являются К третьему типу относятся '''праволинейные (автоматные)''' или '''регулярные грамматики''' (англ.''regular grammars'') {{---}} самые простые из формальных грамматик, которые задают [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярные языки]]. Они являются контекстно-свободными, но с ограниченными возможностями. Все регулярные грамматики могут быть разделены на два эквивалентных класса следующего вида:
{{Определение
|definition =
'''Праволинейные Леволинейная грамматика''' (автоматные) грамматикиангл. ''left-regular grammar'' ) {{---}} это те формальные грамматикиформальная грамматика, всякое правило из <tex>P</tex> которых которой имеет вид <tex>A \rightarrow tBB\gamma</tex> либо или <tex>A \rightarrow t\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 \in Ngamma</tex>, где <tex>t\gamma \in \Sigma , A, B \in N</tex>.}}Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык уже не обязан быть регулярным. Также можно [[Правоконтекстные_грамматики,_эквивалентность_автоматам|показать]], что множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых [[Детерминированные конечные автоматы|конечными автоматами]]. ===Пример===<tex>L</tex> для регулярного выражения <tex>a^*bc^*</tex>. Продукции: <tex>S \rightarrow aS\ |\ bA \\A \rightarrow \varepsilon\ |\ cA</tex> == См. также ==* [[Правоконтекстные грамматики, эквивалентность автоматам]]* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
== Распознавание Источники информации==Для языков* ''А. Ахо, которые задаются грамматиками из иерархии Хомского, есть машины, которые их распознаютДж. Ульман. Следующая таблица обощает классы иерархии Хомского, языки, которые ими задаются'' Теория синтаксического анализа, перевода и машиныкомпиляции. Синтаксический анализ. Том 2. Пер. с англ. — М.: Книга по Требованию, которые распознают эти языки2012.{| class="wikitable"|— ISBN 978-5-458-! Грамматика! Языки! Машина|27407-4| Класс 0| * [[ Перечислимые языки wikipedia:Chomsky_hierarchy| рекурсивно перечислимые Wikipedia {{---}} Chomsky hierarchy]]| * [[httpwikipedia://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| [[Регулярные языки: два определения и их эквивалентность|регулярные}} Иерархия Хомского]]| [[Детерминированные конечные автоматы|конечные автоматы]]|}
== Источники ==[[Категория: Теория формальных языков]]Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.[[Категория: Мир, 1978. Контекстно- Т. 1,2.свободные грамматики]][[Категория: Базовые понятия о грамматиках]]
442
правки

Навигация