[28.03.11] Лекция №8 (Конспекты - Теория формальных языков)

Лекция №8 [28.03.11]

Леммы о разрастании

Язык , является ли он КС-языком или регулярным языком?

Регулярность:

1) предъявить регулярную грамматику;

2) предъявить выражение, описывающее этот язык;

3) построить конечный автомат и по теореме Клинни;

Леммы о разрастании позволяют доказать, что язык НЕ принадлежит КС или регулярным.

Если - регулярный язык, то есть константа , что когда слова становятся больше , то к ним применима лемма о разрастании:

и

Доказательство: - РЯ, значит, по теореме Клини: ,

В графе КА ровно вершин, следовательно, любой путь длинны больше не является простым и содержит контур.

. Вполне может быть, что и .

Пример: , пусть слово достаточно длинное

схема с разрастающимися словами

Если язык регулярен, в нём найдётся множество слов, длины которого образуют арифметическую прогрессию.

Лемму о разрастании нельзя применять для доказательства регулярности некоторого языка, её можно использовать только для доказательства нерегулярности.

Пример: каждое слово языка содержит одинаковое количество букв и расположенных в произвольном порядке. Возьмём РЯ , возьмём , а пересечение двух РЯ является РЯ.

, но он нерегулярен, мы его только что исследовали, значит, тоже нерегулярен.

Пример:

Пусть - достаточно большое и ( ) удовлетворяет лемме о разрастании.

Подцепочка может располагаться только среди букв в силу неравенства .

Цепочка - это некоторое количество среди букв .

А цепочка сначала состоит из , а потом ( ).

Возьмём (выкинем цепочку (один раз мы имеем право это сделать)).

Слово имеет вид , значит, .

Лемма о разрастании для КС-языков

Построим мотивирующий пример:

Посмотрим деревья вывода:

Если мы фиксируем некоторую длину вывода, то длина цепочки, которую мы можем получить, тоже фиксированная.

Средством анализа КС-грамматик у нас будут вот такие деревья вывода.

Зафиксируем следующее утверждение: для заданной КС-грамматики множество выводов заданной длины конечно. Почему? Множество нетерминалов грамматики конечно. Все правила, стоящие в правой части, имеют ограниченную длину, следовательно, для вывода фиксированной длины существует максимально возможная длина цепочки, получаемой в результате этого вывода.

Ещё лемма о разрастании

Для любого контекстно сводобного языка существует константа , такая, что любая цепочка , представляется в виде соединения пяти цепочек , где ,

Доказательство:

Зафиксируем произвольный нетерминал и рассмотрим множество всех выводов, начинающихся с , таких, что высота дерева вывода не превышает количество нетерминалов +1 ( )

Множество , поскольку длина вывода в данном случае ограничена, то есть, - есть конечное множество конечных выводов.

Рассмотрим множество выводов . конечно, значит и конечно.

Рассмотрим множество всех цепочек , которые являются заключительными цепочками выводов из множества . В силу конечности множества , тоже конечно.

Введём константу , то есть, - есть наибольшая длина цепочки из множества .

,

В силу выбора константы , любое дерево вывода цепочки из аксиомы имеет высоту больше, чем . Зафиксируем некоторое дерево вывода с этой цепочки. В этом дереве есть такой нетерминал , что высота вывода из него некоторой подцепочки в точности равна . Поскольку высота дерева больше, чем количество нетерминалов в грамматике, то найдётся такой нетерминал , который в этом дереве вывода встречается хотя бы два раза. И высота вывода из него может быть равна , если совпадает с , либо может быть меньше, чем .

чтотоещё

, значит,

Покажем, что . Не нарушая общности, мы можем предполагать, что грамматика задана в приведённой форме (то есть, -правило применяется только один раз, при выводе пустого слова из аксиомы, и в грамматике нет цепных правил). Заметим, что высота дерева в точности равна 1, а рассматриваемая высота дерева строго больше 1 (хотя бы один-то нетерминал должен быть ( )). Пусть , это означает, что из за некоторое количество шагов можно получить , а такой вывод может существовать только при наличии цепных правил, что в нашей грамматике места не имеет, следовательно, (или или – непустая цепочка).