442
правки
Изменения
→См. также
{{Определение
|definition=
'''Иерархия Хомского''' — (англ. ''Chomsky hierarchy'') {{---}} классификация [[формальные грамматики|формальных грамматик]] и [[формальные грамматики|задаваемых ими языков]], согласно которой они делятся на 4 класса по их условной сложности.
}}
== Класс 0 ==
Практического применения в силу своей сложности такие грамматики не имеют.
===Пример===
Продукции:
<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 \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 \rightarrow \varepsilon</tex>, но тогда <tex>S</tex> не встречается в правых частях правил).
}}
Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
===Пример===
<tex>
S \rightarrow 012 \\
S \rightarrow 0TS2 0AS2 \\T0 A0 \rightarrow 0T 0A \\ T1 A1 \rightarrow 11
</tex>
== Класс 2 ==
Второй класс составляют [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободные грамматики]]. Type-2 grammars (context-free grammars) generate the context-free languages. These are defined by rules of the form A \rightarrow \gamma with A a nonterminal and \gamma a string of terminals and/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Эти языки распознаются с помощью [[Автоматы_с_магазинной_памятью|автоматов с магазинной памятью]].
{{Определение
|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 ==
== См. также ==
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языкиПравоконтекстные грамматики, эквивалентность автоматам]]
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]