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