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