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