Рассмотрим несколько примеров применения теоремы о разрастании.
Пример 6.4. Покажем, что язык L1 ={ w =0i 1i | i
1 } не является автоматным.
Предположим, что он автоматный. Тогда для него имеется n из утверждения теоремы 6.3. Рассмотрим следующее ("специальное" !) слово w = 0n 1n. Очевидно, что w
L1. Предположим, что существует разбиение w = xyz, удовлетворяющего условиям (1) и (2) теоремы. Так как по условию (2) |xy|
n, то y = 0i для некоторого i>0. Но тогда слово w0 = xz= 0n-i1n
L1, что противоречит условию (3) теоремы. Следовательно язык L1 не автоматный.
Пример 6.5. Покажем, что язык СКОБ правильных скобочных последовательностей в алфавите { (, ) } не является автоматным.
Схема доказательства та же. В качестве специального слова выберем слово w = (n )n, оно, очевидно, принадлежит СКОБ. Тогда для всякого разбиения w = xyz такого, что |xy|
n слово y = (i для некоторого i>0. И, как и в предыдущем примере, слово w0 = xz= (n-i)n
СКОБ, что противоречит условию (3) теоремы. Следовательно, язык СКОБ не автоматный.
Пример 6.6.
Покажем, что язык L2 ={ w =0i 1j | i
2j+1 } не является автоматным.
Здесь, предположив, что L2 автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово w = 0{2n+1}1n
L2. Для всякого разбиения w = xyz такого, что |xy|
n слово y = 0i для некоторого i>0. Рассмотрим слово w2 = x y2 z = 0{2n+1+i}1n. Но
. Следовательно, w2
L2 и язык L2 не является автоматным.
Пример 6.7. Рассмотрим язык "квадратов" в унарном алфавите { | }:
Здесь, предположив, что L3 автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово w = |{n2}. Для всякого разбиения w = xyz такого, что |xy|
n слово y = |i для некоторого 0 < i
n. Тогда
. Но n2 - i
n2 -n > n2 -2n +1 =(n-1)2. Следовательно, n2 - i не является полным квадратом и w0
L3, т.е. язык "квадратов" L3 не является автоматным.
Пример 6.8.
Рассмотрим язык "простых чисел" в унарном алфавите { | }:
Предположим, что Lpr - автоматный язык и зафиксируем для него константу n из теоремы 6.3.
Выберем простое число p > n и рассмотрим слово w = |p. Пусть w = xyz - произвольное разбиение w такое, что |xy|
n. Тогда для некоторого 0 < i
n слово y = |i и xz = |p -i. Положим k = p - i и рассмотрим слово wk = x yk z. Его длина p' равна |x| +k|y| + |z|= (p-i)(i+1). Так как 1
i < n+1
p, то p' - составное число и wk
Lpr. Следовательно, Lpr - не автоматный язык. Заметим, что в этом примере k выбирается для каждого n по-своему. Еще один прием доказательства неавтоматности языка L состоит в том, чтобы вместо L рассмотреть некоторый язык L' = op(L,L1,… , Lk), полученный из L и автоматных языков L1,… , Lk
с помощью операций op, сохраняющих автоматность. Если доказать, что L' не является автоматным, то и исходный язык L не автоматен. Пример 6.9. Рассмотрим язык L4 ={ 0i 1j | i
j }. Пусть L5= {0i1j | i
1, j
1}. Очевидно, что язык L5 автоматный. Нетрудно заметить, что его пересечение с дополнением L4 совпадает с языком L1
из примера 6.4, т.е. L1 = L5
overline{L4}. Так как мы установили, что L1 не автоматный, то и L4 не является автоматным. Являются ли условия теоремы 6.3 достаточными для того, чтобы язык оказался автоматным? Следующий пример показывает, что ответ на этот вопрос отрицателен. Пример 6.10.Пусть L6 ={cr ai bi | r
1 , i
0 }, L7= { aibj | i
0, j
0}. Рассмотрим язык L8 = L6
L7. Для этого языка можно в качестве n выбрать 1. Каждое слово w из L8 принадлежит L6 или L7. Если слово w= cr ai bi
L6 , то оно представимо в виде xyz, где x=?, y=c, z= cr-1 ai bi ( r
1, i
0 ). Тогда w0 = z= cr-1 ai bi ( r
1, i
1 ) и при r=1 слово w0 = ai bi
L7, а при r > 1, очевидно, w0
L6. При k
1 имеем wk =cr+k-1 ai bi
L6. Если слово w= ai bj
L7 и i
1, то его можно представить как в виде xyz, где x=?, y=a, z= ai-1 bj ( i
1, j
0 ) и для каждого k
0 wk = aka i-1 bj
L7. Если же i =0, то w= bj ( j
1 ) и его можно разбить на части x=?, y=b, z= bj-1 ( j
1 ). И в этом случае для каждого k
0 wk =bk bj-1
L7. Во всех случаях wk
L8 и, следовательно язык L8 удовлетворяет условиям теоремы 6.3.
Но этот язык не автоматный. Действительно, пусть
: {a, b, c}*
{0, 1 }* - это гомоморфизм, заданный как
(a)=0,
(b) = 1,
(c) =?. Тогда
(L8 \ L7) =
(L6) = L1 из примера 6.4. Так как язык L7 является автоматным, а L1 - нет, то и язык L8 не является автоматным.
