Праволинейная грамматика — в теории конечных автоматов — специальный случай регулярной грамматики.
Определение
Грамматика называется праволинейной, если она содержит только правила вида А→а, А→аВ.
Теорема
Класс языков, порождаемых праволинейными грамматиками, совпадает с классом регулярных языков.
Доказательство
→ Пусть А=(Σ, Q, δ, s, T) — детерминированный конечный автомат δ(q1,a1)=q2
все слова из s в Т образуют L(А) — язык
для каждой дуги графа А поставим в соответствие правило вывода q1→a1q2
q→ε для каждой q из Т
s — аксиома
s →*wq, q из Т
взяли путь, по построению можем построить вывод, w порождается выводом
← Если праволинейная грамматика содержит правило А→а, то его можно заменить правилами A→aC, С→ε, где С новый нетерминал. Этим правилам ставим в соответствие дуги графа.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .