Математическая теория формальных языков


           

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


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



Содержание  Назад  Вперед





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий