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

Пример 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* определяются понятия побуквенного гомоморфизма и локального языка и доказывается еще один критерий автоматности: среди языков, не содержащих пустого слова, автоматными являются в точности образы локальных языков при побуквенных гомоморфизмах.

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