Математическая теория формальных языков
Нормальная форма праволинейных грамматик
Определение 2.5.1.
Праволинейная грамматика в нормальной форме (автоматная грамматика, регулярная грамматика, finite-state grammar) - это праволинейная грамматика, в которой каждое правило имеет вид , , или , где , , .
Теорема 2.5.2.
Каждая праволинейная грамматика эквивалентна некоторой праволинейной грамматике в нормальной форме.
Доказательство. Применим последовательно теорему 2.4.3, лемму 2.3.3 и воспользуемся конструкцией из доказательства теоремы 2.4.1.
Теорема 2.5.3.
Если праволинейный язык не содержит пустого слова, то он порождается некоторой праволинейной грамматикой в нормальной форме без -правил.
Упражнение 2.5.4. Найти праволинейную грамматику, эквивалентную грамматике
Упражнение 2.5.5. Найти праволинейную грамматику в нормальной форме без -правил, порождающую язык
Упражнение 2.5.6. Найти праволинейную грамматику в нормальной форме без -правил, порождающую язык
