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

Рассмотрим несколько примеров применения теоремы о разрастании.

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

(L8 \ L7) =

(L6) = L1 из примера 6.4. Так как язык L7 является автоматным, а L1 - нет, то и язык L8 не является автоматным.

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