Свойства замкнутости класса автоматных языков



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


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



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


ЗНАЕТЕ ЛИ ВЫ?

Свойства замкнутости класса автоматных языков



Теорема 3.1.1. Класс автоматных языков замкнут относительно итерации, конкатенации и объединения.

Доказательство. Без ограничения общности можно предположить, что каждый из исходных языков задан конечным автоматом с одним начальным и одним заключительным состоянием. Тогда во всех трех случаях результирующий автомат получается из исходных путем добавления нескольких -переходов и состояний и назначения новых начальных и заключительных состояний.

Пример 3.1.2. Пусть . Рассмотрим конечный автомат

где

Тогда язык L(M1)* распознается конечным автоматом .

Пример 3.1.3. Пусть . Рассмотрим конечный автомат M1 из примера 3.1.2 и конечный автомат

где

Тогда язык распознается конечным автоматом

а язык распознается конечным автоматом

Пересечение и дополнение автоматных языков

Теорема 3.2.1. Класс автоматных языков замкнут относительно дополнения и пересечения.

Доказательство. Если язык L распознается полным детерминированным конечным автоматом , то язык распознается конечным автоматом .

Пересечение выражается через объединение и дополнение (закон де Моргана).

Замечание 3.2.2. Автоматность пересечения двух автоматных языков можно легко доказать и без привлечения теоремы 2.7.1. Для этого достаточно построить по двум конечным автоматам с однобуквенными переходами

новый конечный автомат

где

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

Лемма 3.3.1 (pumping lemma, лемма о разрастании, лемма о накачке, лемма-насос). Пусть L автоматный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова длины не меньше pможно подобрать слова , для которых верно xyz = w, , и для всех .

Доказательство. Пусть язык L распознается конечным автоматом , содержащим только переходы с метками длины единица. Положим p = |Q|. Пусть слово w является меткой успешного пути

и . Согласно принципу Дирихле найдутся такие индексы j и k, что и qj = qk(ведь множество индексов содержит p+1 натуральных чисел, а значения qi берутся из множества, содержащего всего p элементов). Выберем слова x, y и z так, что |x| = j, |y| = k - j и xyz = w.

Пример 3.3.2. Пусть . Рассмотрим автоматный язык

Положим p = 3. Тогда для любого слова длины не меньше p найдутся слова , соответствующие утверждению леммы 3.3.1. Действительно, если w = abu для некоторого слова u, то положим , y = ab, z = u ; иначе w = aabu и можно положить x = a, y = ab, z = u.

Примеры неавтоматных языков

Пример 3.4.1. Рассмотрим язык над алфавитом . Утверждение леммы 3.3.1 не выполняется ни для какого натурального числа p. Действительно, если w = abpap, то x = abk, y = bm, z = bp-k-map для некоторых и или , y = abl, z = bp-lap для некоторого . В обоих случаях . Таким образом, язык L не является автоматным.

Замечание 3.4.3. Условие, сформулированное в лемме 3.3.1, является необходимым для автоматности, но не достаточным.

Пример 3.4.4. Пусть . Рассмотрим язык L = {akbman | k=0 или m=n}. Положим p = 1. Тогда для любого слова длины не меньше p найдутся слова , соответствующие утверждению леммы 3.3.1. Тем не менее язык L не является автоматным, так как

Лемма 3.4.5*. Пусть L - автоматный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова можно подобрать слова , для которых верно xyz = w, и для всех . Здесь [m] означает целую часть числа m.

Доказательство. Пусть L распознается конечным автоматом , содержащим только переходы с метками длины единица. Положим p = |Q|. Пусть слово w является меткой успешного пути . Обозначим l = [|w|/p]. Если l = 0, то положим и . Пусть . Согласно принципу Дирихле найдутся такие натуральные числа j и k, что и qjl = qkl. Выберем слова x, y и z так, что |x| = jl, |y| = kl - jl и xyz = w.

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

В разделе 4.2* определяются понятия побуквенного гомоморфизма и локального языка и доказывается еще один критерий автоматности: среди языков, не содержащих пустого слова, автоматными являются в точности образы локальных языков при побуквенных гомоморфизмах.

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



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

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