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

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

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

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

где

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

Пример 3.1.3. Пусть . Рассмотрим конечный автомат M₁ из примера 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, что и q_j = q_k(ведь множество индексов содержит p+1 натуральных чисел, а значения q_i берутся из множества, содержащего всего 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 = ab^pa^p, то x = ab^k, y = b^m, z = b^p-k-ma^p для некоторых и или , y = ab^l, z = b^p-la^p для некоторого . В обоих случаях . Таким образом, язык L не является автоматным.

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

Пример 3.4.4. Пусть . Рассмотрим язык L = {a^kb^maⁿ | 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, что и q_jl = q_kl. Выберем слова x, y и z так, что |x| = jl, |y| = kl - jl и xyz = w.

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

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

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