Математическая теория формальных языков
Лемма о разрастании для линейных языков
Определение 9.2.1.
Линейная грамматика в нормальной форме - это такая линейная грамматика, в которой каждое правило имеет вид , ,
или , где , , .
Теорема 9.2.2.
Каждая линейная грамматика эквивалентна некоторой линейной грамматике в нормальной форме.
Теорема 9.2.3.
Если линейный язык не содержит пустого слова, то он порождается некоторой линейной грамматикой в нормальной форме без -правил.
Теорема 9.2.4.
Язык L является линейным тогда и только тогда, когда язык
является линейным. \end{theorem}
Лемма 9.2.5.
Пусть L - линейный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова
длины не меньше p можно подобрать слова , для которых верно uvxyz = w,
(то есть или ),
и
для всех .
Доказательство. Пусть язык
порождается линейной грамматикой в нормальной форме
без -правил. Положим p = |N| + 1. Пусть
и . Зафиксируем некоторое дерево вывода слова w в грамматике G. Рассмотрим самый длинный путь в этом дереве (он начинается с корня и заканчивается некоторым листом, помеченным символом из ). Этот путь содержит не менее |N| + 1 вершин, помеченных элементами N. Среди первых |N| + 1 вершин рассматриваемого пути найдутся две вершины с одинаковыми метками. Выберем слова u, v, x, y и z так, что uvxyz = w, поддерево с корнем в одной из найденных вершин имеет крону x и поддерево с корнем в другой найденной вершине имеет крону vxy.
Пример 9.2.6.
Рассмотрим язык
над алфавитом {a,b}. Утверждение леммы 9.2.5 не выполняется ни для какого натурального числа p. Следовательно, язык L не является линейным.
Упражнение 9.2.7. Какому классу принадлежит язык
Упражнение 9.2.8. Какому классу принадлежит язык
Упражнение 9.2.9. Какому классу принадлежит язык
