Множества двусторонних контекстов

Определение 6.3.1. Пусть и . Тогда множество контекстов (множество двусторонних контекстов) слова y относительно языка L определяется следующим образом:

Пример 6.3.2. Пусть и . Тогда

Лемма 6.3.3. Если , то .

Доказательство. Из определений следует, что

Лемма 6.3.4. Если , то и .

Доказательство. Пусть и . Тогда . Следовательно, . Далее, получаем, что , и . Второе равенство доказывается аналогично.

Лемма 6.3.5. Если и , то .

Определение 6.3.6. Пусть . Тогда множество

называется синтаксическим моноидом (syntactic monoid) языка L.

Определение 6.3.7*. Полугруппой (semigroup) называется непустое множество M с ассоциативной бинарной операцией .

Определение 6.3.8*. Пусть - полугруппа. Элемент называется единицей (unit), если для каждого .

Определение 6.3.9*. Моноид - это полугруппа с единицей .

Теорема 6.3.10*. Определим бинарную операцию на Synt(L) следующим образом:

Тогда является моноидом.

Теорема 6.3.11. Синтаксический моноид Synt(L) конечен тогда и только тогда, когда язык L является автоматным.

Доказательство Пусть множество Synt(L) конечно. Согласно лемме 6.3.3 множество тоже конечно. В силу леммы 6.1.6 язык L является автоматным.

Обратно, пусть язык L распознается некоторым конечным автоматом , не содержащим переходов с метками длины больше единицы. Поставим в соответствие каждому слову y множество , определенное следующим образом:

Легко проверить, что если , то . Следовательно, , где n = |Q|.

Пример 6.3.12. Рассмотрим конечный автомат M из примера 2.1.14. Тогда

1. ;

2. если , то ;

3. если , то ;

4. если , то ;

5. если , то ;

6. ;

7. .

Лемма 6.3.13. Пусть , и для каждого слова длины n найдется такое слово , что и . Тогда

Доказательство. Индукцией по можно доказать, что для каждого слова длины k найдется такое слово , что и . В шаге индукции используется лемма 6.3.5.

6.4*. Классы эквивалентности слов

Лемма 6.4.1. Пусть и . Тогда

Определение 6.4.2. Пусть и . Обозначим через язык . Обозначим через язык .

Пример 6.4.3. Пусть . Множества вида образуют разбиение множества на классы эквивалентности. Множества вида образуют разбиение множества на классы эквивалентности.

Пример 6.4.4. Пусть и . Тогда

Лемма 6.4.5. Если язык является автоматным, то для каждого слова языки и являются автоматными.

Доказательство. Пусть язык L распознается конечным автоматом , не содержащим переходов с метками длины больше единицы. Будем использовать обозначение Tr_M из доказательства теоремы 6.3.11. При любой фиксированной паре язык является автоматным (он распознается конечным автоматом ). Для каждого слова язык является автоматным, так как он представим в виде пересечения конечного семейства автоматных языков:

Каждый из языков [x]_L и является объединением конечного семейства автоматных языков:

Замечание 6.4.6. Из теоремы 6.1.8 вытекает, что если язык L автоматный, то существует лишь конечное число различных множеств . Аналогичное утверждение верно для множеств (см. теорему 6.3.11).

Пример 6.4.7. Рассмотрим язык

над алфавитом . Тогда

Теорема 6.4.11. Язык является автоматным тогда и только тогда, когда существует такое отношение эквивалентности , что R разбивает на конечное множество классов эквивалентности, L является объединением некоторых из этих классов эквивалентности и для любых , , из xRy следует xzRyz.

Замечание 6.4.12. Теоремы 6.1.8 и 6.4.11 образуют теорему Майхилла-Нерода.

Перейдем к более богатому классу языков - к контекстно-свободным языкам. Они находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста, поисковые системы.

Начнем рассмотрение контекстно-свободных языков с введения понятия деревьев вывода, что позволит определить важное для компьютерных приложений понятие однозначности контекстно-свободной грамматики. Чтобы не вдаваться в детали определения изоморфизма ориентированных деревьев, будем использовать в определении однозначности понятие левостороннего вывода (раздел 7.2). Соответствие деревьев вывода и левосторонних (а также правосторонних) выводов понадобится также в "лекции 13".

Из класса всех контекстно-свободных языков можно выделить подкласс тех языков, для которых существует хотя бы одна однозначная грамматика. В разделе 7.3* доказывается, что все праволинейные (то есть автоматные) языки принадлежат этому подклассу.

В последнем разделе этой лекции приводятся важные конкретные примеры однозначных контекстно-свободных грамматик, моделирующих системы правильно вложенных скобок и польскую (префиксную) запись выражений.

Деревья вывода

Определение 7.1.1. Выводам в контекстно-свободной грамматике соответствуют так называемые деревья вывода (деревья разбора, derivation tree, parse tree) - некоторые упорядоченные деревья, вершины которых помечены символами алфавита . Корень дерева отвечает начальному символу. Каждому символу слова w₁, на которое заменяется начальный символ на первом шаге вывода, ставится в соответствие вершина дерева, и к ней проводится дуга из корня. Полученные таким образом непосредственные потомки корня упорядочены согласно порядку их меток в слове w₁. Для тех из полученных вершин, которые помечены символами из множества N, делается аналогичное построение, и т. д.

Кроной (yield) дерева вывода называется слово, записанное в вершинах, помеченных символами из алфавита .

Пример 7.1.2. Рассмотрим контекстно-свободную грамматику

Выводу соответствует следующее дерево вывода.

Крона этого дерева вывода - ababab.