3622
правки
Изменения
м
→Класс 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>.
}}
Оба вида задают одинаковые языки. При этом если правила леволинейной и праволинейной грамматик объединить, то язык будет уже не обязан быть регулярным.
Также можно [[Правоконтекстные_грамматики,_эквивалентность_автоматам|показать]], что множество языков, задаваемых праволинейными грамматиками, совпадает со множеством языков, задаваемых [[Детерминированные конечные автоматы|конечными автоматами]].
