Изменения

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

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

374 байта добавлено, 12:39, 11 марта 2018
См. также
===Пример===
Терминалы: <tex>\Sigma = \{a, c, d\}</tex>
 
Нетерминалы: <tex>N = \{S, A, B\}</tex>
 
Продукции:
<tex>
S \rightarrow aBc aBcc \\aB B \rightarrow cA A \\BAA \rightarrow d \\Ac \rightarrow dB \\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 ==
Языки, заданные этими грамматиками, распознаются с помощью '''линейно ограниченного автомата''' (англ. ''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>\{S, A\}</tex>
Продукции:
== См. также ==
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языкиПравоконтекстные грамматики, эквивалентность автоматам]]
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]
442
правки

Навигация