Введение в схемы, автоматы и алгоритмы



             

Примеры неавтоматных языков - часть 2


Выберем простое число 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.


Содержание  Назад  Вперед