442
правки
Изменения
→См. также
===Пример===
<tex>L=\{w \in \Sigma^* | \mid w = 0^n1^n2^n, n \geqslant 1\}</tex>
Продукции:
===Пример===
<tex>L=\{w \in \Sigma^* | \mid w = w^R\}</tex> (язык палиндромов).
Продукции: <tex>S\rightarrow\alpha S\alpha\,|\,\alpha\,|\,\varepsilon, \alpha \in \Sigma</tex>
'''Праволинейная грамматика''' (англ. ''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>.
}}
Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык будет уже не обязан быть регулярным.
Также можно [[Правоконтекстные_грамматики,_эквивалентность_автоматам|показать]], что множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых [[Детерминированные конечные автоматы|конечными автоматами]].
== См. также ==
* [[Разрешимые_(рекурсивные)_языки|Разрешимые (рекурсивные) языкиПравоконтекстные грамматики, эквивалентность автоматам]]
* [[Возможность_порождения_формальной_грамматикой_произвольного_перечислимого_языка|Возможность порождения формальной грамматикой произвольного перечислимого языка]]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Базовые понятия о грамматиках]]
