Математическая теория формальных языков

       

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


Пример 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.2.

Пусть . При каких словах

и

язык

является автоматным?

Замечание 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.

Упражнение 3.4.6. Является ли автоматным язык

Упражнение 3.4.7. Является ли автоматным язык

Упражнение 3.4.8. Является ли автоматным язык

множества

и

равномощны?

Упражнение 3.4.9. Является ли автоматным язык

множества

и

равномощны?

Упражнение 3.4.10. Является ли автоматным язык

Упражнение 3.4.11. Является ли автоматным язык, порождаемый грамматикой



Содержание раздела