Праволинейная грамматика

Праволинейная грамматика — в теории конечных автоматов — специальный случай регулярной грамматики.

Определение

Грамматика называется праволинейной, если она содержит только правила вида А→а, А→аВ.

Теорема

класс языков, порождаемых праволинейными грамматиками совпадает с классом регулярных языков.

Доказательство

→ Пусть А=(Σ, Q, δ, s, T) — детерминированный конечный автомат δ(q1,a1)=q2

все слова из s в Т образуют L(А) — язык

для каждой дуги графа А поставим в соответствие правило вывода q1→a1q2

q→ε для каждой q из Т

s — аксиома

s →*wq, q из Т

взяли путь, по построению можем построить вывод, w порождается выводом

← Если праволинейная грамматика содержит правило А→а, то его можно заменить правилами A→aC, С→ε, где С новый нетерминал. Этим правилам ставим в соответствие дуги графа.