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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



Определение 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 распознается конечным автоматом , не содержащим переходов с метками длины больше единицы. Будем использовать обозначение TrM из доказательства теоремы 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) - некоторые упорядоченные деревья, вершины которых помечены символами алфавита . Корень дерева отвечает начальному символу. Каждому символу слова w1, на которое заменяется начальный символ на первом шаге вывода, ставится в соответствие вершина дерева, и к ней проводится дуга из корня. Полученные таким образом непосредственные потомки корня упорядочены согласно порядку их меток в слове w1. Для тех из полученных вершин, которые помечены символами из множества N, делается аналогичное построение, и т. д.

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

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

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

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



Последнее изменение этой страницы: 2021-04-04; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.68.118 (0.034 с.)