Нормальная форма праволинейных грамматик

Определение 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. Найти праволинейную грамматику в нормальной форме без -правил, порождающую язык