Изменения

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

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

278 байт убрано, 12:39, 11 марта 2018
См. также
===Пример===
Терминалы: <tex>\Sigma = \{a, c, d\}</tex>
 
Нетерминалы: <tex>N = \{S, A, B\}</tex>
 
Продукции:
</tex>
Выведем в данной грамматике строку <tex>w = 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 aBcc Rightarrow a\rightarrow aAcc boldsymbol{A} \rightarrow aBc Rightarrow ad\rightarrow aAc boldsymbol{B} \rightarrow aB Rightarrow ad\rightarrow aA boldsymbol{A} \rightarrow adB Rightarrow ad\rightarrow adA boldsymbol{A}AA \rightarrow adAAA Rightarrow add\rightarrow addBAA boldsymbol{BAA} \rightarrow Rightarrow addd</tex>
== Класс 1 ==
Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''linear bounded automaton'') (недетерминированная машина Тьюринга, чья лента ограничена константой, зависящей от длины входа.)
Как будет показано [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность|в другом конспектеИзвестно]], что неукорачивающие грамматики эквивалентны контекстно-зависимым.
===Пример===
Язык <tex>L=\{w \in \Sigma^* | \mid w = 0^n1^n2^n, n \geqslant 1\}</tex> Терминалы: <tex>\Sigma = \{0, 1, 2\}</tex> Нетерминалы: <tex>N = \{S, A\}</tex>
Продукции:
'''Контекстно-свободная грамматика''' (англ. ''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>\Sigma</tex> Нетерминалы: <tex>N = \{S\}</tex>
Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>;
== Класс 3 ==
'''Праволинейная грамматика''' (англ. ''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>.
}}
Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык будет уже не обязан быть регулярным.
Также можно [[Правоконтекстные_грамматики,_эквивалентность_автоматам|показать]], что множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых [[Детерминированные конечные автоматы|конечными автоматами]].
===Пример===
Язык <tex>L</tex> для регулярного выражения <tex>a^*bc^*</tex>. Терминалы: <tex>\Sigma = \{a, b, c\}</tex> Нетерминалы: <tex>N = \{S, A\}</tex>
Продукции:
== См. также ==
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языкиПравоконтекстные грамматики, эквивалентность автоматам]]
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]
295
правок

Навигация