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

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

Пример 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 не является автоматным.

Теорема о разрастании для автоматных языков

До сих пор мы встречались лишь с автоматными языками и накопили достаточно много средств для доказательства того, что некоторый язык является автоматным. Для этого, например, достаточно построить для него регулярное выражение или получить его с помощью различных рассмотренных выше операций из заведомо автоматных языков. В этом разделе мы установим некоторое необходимое условие, которому удовлетворяют все автоматные языки. После этого, проверив, что некоторый язык этому условию не удовлетворяет, можно заключить, что он не является автоматным.

Теорема 6.3. (о разрастании для автоматных языков)

Пусть L - бесконечный автоматный язык. Тогда существует такая константа n, что любое слово w

L длины |w| > n можно разбить на три части x, y и z так, что w = xyz и

|xy|

n;|y| > 0;для любого m 0 слово wm = x ym z принадлежит языку L.

(Здесь y0= ?, y1=y, yi+1 = yiy).

Доказательство Так как язык L автоматный, то существует ДКА A=<?, Q, q0, F, ? >, распознающий L. Пусть |Q|= n и слово w=w1w2 … wk

L имеет длину k > n. Рассмотрим путь

в диаграмме A, который несет слово w. Очевидно, что среди первых (n+1) состояний этого пути хотя бы одно встречается дважды. Выберем первое из таких состояний q

Q. Тогда для некоторой пары чисел l < j n имеем . Пусть x=w1w2 … wl - это префикс w, который переводит q0 в , - это подслово w, которое переводит в , и - это суффикс w, который переводит в . x и z могут быть пусты, но |y| = j-l 1. Длина |xy| = j n. Таким образом, условия (1) и (2) теоремы выполнены. Нетрудно убедиться и в выполнении условия (3). Действительно, выбросив из пути p цикл получим путь p0 из q0 в , который несет слово xz, а повторив этот цикл m раз, получим путь p0 из q0 в q{ik} F, который несет слово xym z. Следовательно, для любого m 0 wm = x ym z L.

Содержательно, эта теорема утверждает, что у всякого достаточно длинного слова из автоматного языка имеется непустое подслово, которое можно вырезать или повторить сколько угодно раз, оставаясь внутри языка. Как, используя теорему ref{th-razr}, доказать, что некоторый язык L не является автоматным? Это можно сделать, используя схему доказательства "от противного":

Предположим, что L автоматный язык. Тогда для него имеется константа n из утверждения теоремы ref{th-razr}.Определим по n некотрое "специальное" слово w из L длины > n и докажем, что для любого разбиения w = xyz, удовлетворяющего условиям (1) и (2) теоремы, найдется такое k 0, что слово wk=xyk z не принадлежит L.На основании полученного противоречия делаем вывод, что L - не автоматный язык.

Разумеется, в этой схеме самым сложным является выбор "специального" слова w в пункте (2). Что касается, подбора такого k 0, для которого wk L, то, как правило, достаточно рассмотреть k = 0 или k = 2.

Примените процедуру детерминизации из теоремы

Задача 6.1. Примените процедуру детерминизации из теоремы 4.2 и постройте ДКА, эквивалентный построенному выше в примере 6.2 НКА M.
Задача 6.2. Цилиндрификация - это операция, которая обратна проекции. Для любых алфавитов ? и ? таких, что ? ?, и любого языка L в алфавите ? определим его цилиндрификацию как язык CYL?(L) = {w ?* | при вычеркивании из w всех букв, не входящих в ?, получается слово u L).
Показать, что для автоматного языка L язык CYL?(L) также является автоматным языком. Предложите процедуру перестройки автомата, распознающего L , в автомат, распознающий CYL?(L).
Задача 6.3.
Обращением слова w=w1w2 … wk (wi ?, i=1, … , k) называется слово w{-1}= wk … w2 w1. Показать, что для автоматного языка L его обращение - язык L{-1} ={ w{-1} | w L} также является автоматным языком.
Задача 6.4.
Пусть L - автоматный язык в алфавите ?. Доказать, что автоматными являются и следующие языки:
ПРЕФ(L) = {w | существует такое слово x ?*, что wx L}.СУФ(L) = {w | существует такое слово x ?*, что xw L}.КОР(L) = {w | существуют такие слова x, y ?*, что xwy L}.MAX(L) = {w | w L и для всякого непустого x слово wx L}.
Задача 6.5. Пусть L - автоматный язык в алфавите ?={a1,…, am}, а L1,…, Lm - это автоматные языки в алфавите ?. Доказать, что автоматным является и язык ЗАМ(L), полученный из слов L заменой каждой буквы ai на некоторое слово из Li, т.е. ЗАМ(L) = {w | textit{ существует такое слово }u=a{i1}a{i2}… a{in} L и такие слова w1,w2,…, wn ?*, что w=w1w2… wn и wj L{ij} для всех j=1,2,… n }.
Задача 6.6. Пусть L - автоматный язык в алфавите ?, k - целое положительное число и - отображение ?k в ?. Доказать, что автоматным является язык L1 ={ (a1a2… ak) … (a{(n-1)k+1}a(n-1)k+2 … ank) | a1a2… ank L}.
Задача 6.7. Докажите, что теорема 6.3 о разрастании остается справедливой и при замене условия 1) |xy| n на условие 1') |yz| n, т.е. повторяющееся подслово y имеется и в суффиксе w длины n.
Задача 6.8. Доказать, что следующие языки в алфавите ? ={a, b, c} не являются автоматными.
Множество всех слов, в которых букв a на 3 больше, чем букв b. L={ ancbm | m > 3n }. L={ wcw-1 | w =a2bna для некоторого n > 0}. L={ w | |w| = 2n для некоторого целого числа n }. L={ wc|w| | w {a,b}*, |w| - длина слова w}.
Задача 6.9. ?-выражение - это либо переменная x, или символ ?, за которым следует переменная, а далее либо ?-выражение, либо левая скобка, ?-выражение, еще одно ?-выражение и правая скобка. Например, ? x x, ? x(x x), ? x ? x (? x(x x) ? x(x x)) - это правильные ?-выражения, а (x x), ? x(? x) и ? x((x x) - неправильные. Докажите, что язык ?-выражений в алфавите { x, ?, (, ) } не является автоматным.
Задача 6.10. Выше в задаче строился автомат-распознаватель, который проверял правильность сложения двоичных чисел. Докажите, что для операции умножения двоичных чисел такого автомата не существует, т.е. что язык в алфавите троек битов U = {(x1(1),x2(1),y(1)) (x1(2),x2(2),y(2)) … (x1(n),x2(n),y(n)) | y = y(n) … y(2)y(1) - это первые n битов произведения двоичных чисел x1= x1(n)… x1(2)x1(1) и x2 = x2(n)… x2(2)x2(1)} не является автоматным.
Задача 6.11.
Доказать, что язык L = { w | число букв a в w число букв b в w } в алфавите ? ={a, b} не является автоматным.

Замкнутость относительно гомоморфизмов и их обращений

Обратимся снова к свойствам замкнутости класса автоматных языков. Как мы уже установили с помощью конструкции произведения автоматов, этот класс замкнут относительно объединения, пересечения и разности (см. следствие 4.1.1). Из теоремы 5.1 непосредственно следует, что класс автоматных языков замкнут относительно операций конкатенации и итерации. Можно легко установить, что он также замкнут относительно дополнения.

Предложение 6.1. Пусть L - автоматный язык в алфавите ?. Тогда его дополнение - язык

также является автоматным.

Действительно, достаточно заметить, что язык ?*, включающий все слова в алфавите ? является автоматным и что

.

Определенная ниже операция гомоморфизма формализует идею посимвольного перевода слов одного алфавита в слова другого.

Определение 6.1. Пусть ? и Delta - два алфавита. Отображение

: ?* Delta* слов первого из них в слова второго называется гомоморфизмом, если

(?) = ?; для любых двух слов w1 и w2 в алфавите ? имеет место равенство (w1w2) = (w1)(w2).

Из этого определения непосредственно следует, что гомоморфизм однозначно определяется своими значениями на символах алфавита ?. Если w=w1w2 … wn, wi

? (1 i n), то (w) = (w1)(w2) … (wn).

Пример 6.1.Пусть ? ={a, b, c}, Delta ={ 0, 1}, а гомоморфизм

определен на символах ? следующим образом: (a) =00, (b) =?, (c) =101.

Тогда

(aca) = 0010100, (abcb) =00101, (bbb) = ?.

Определение 6.2.

Пусть

: ?* Delta* - произвольный гомоморфизм и L - язык в алфавите ?. Образом (L) языка L при гомоморфизме называется язык (L)= { (w) | w L}, состоящий из образов всех слов языка L.

Пусть L - язык в алфавите ?. Прообразом этого языка при гомоморфизме

называется язык -1(L)= { w ?* | (w) L}, состоящий из всех таких слов в алфавите ?, чьи образы при гомоморфизме попадают в L.

Оказывается, что класс автоматных языков замкнут относительно операций гомоморфизма и обращения гомоморфизма (взятия прообраза)

Теорема 6.1. Пусть

: ?* ?* - произвольный гомоморфизм и L - автоматный язык в алфавите ?. Тогда и язык (L) вляется автоматным.

Доказательство Пусть A=<?, Q, q0, F, ?> - ДКА, распознающий язык L. Построим по нему НКА M =<?, QM, q0M, FM, ?M>, распознающий язык (L). Идея этого построения проста: нужно каждый переход из состояния q в q' по букве a ? в автомате A превратить в переход из q в q' по слову (a) в автомате M.

Пусть ? = {a1, … , am}, Q= {q0, q1, …, qn} и (ai)= d1id2i … d{ki}i, dli ? (1 l ki) (если (ai) ?). Для каждого ai зафиксируем простой НКА Mi, распознающий язык {d1id2i … d{ki}i}, имеющий (ki +1) состояние p0i, p1i, …, p{ki}i и команды p{l-1}dli pl (1 l ki). ( Если (ai) = ?, то у Mi будут два состояния, соединенные ?-переходом). Теперь для каждой команды qj ai qr поместим в M между qj и qr автомат Mi (цепочку состояний p0i, p1i, …, p{ki}i). Чтобы состояния различных цепочек не склеивались, придадим им верхний индекс j, т.е. у каждого qj будет своя копия каждого из автоматов Mi. Для этого положим QM = Q { plji | 0 j n, 1 i m, 0 l ki }. Таким образом, pl{ji} - это l-ое состояние на пути из qj по "старой" букве ai. Программа ?M автомата M строится по программе A следующим образом. Для каждой команды вида qj ai qr из ? поместим в ?M следующие команды:



Таким образом, из qj автомат M по пустому переходу попадает в начальное состояние p0ji j-ой копии автомата Mi, затем проходит по слову (ai) и снова по пустому переходу попадает в qr.

Для завершения определения M положим q0M = q0 и FM = F.

Докажем теперь, что наше построение корректно, т.е., что (L)=( LA) = LM .



(L) LM. Заметим вначале, что если ? L, то q0 F и по определению q0 FM, следовательно (?)=? LM.

Пусть w=w1w2… wk L, ws ?. Тогда в диаграмме A имеется путь из q0 в некоторое заключительное состояние q' F, который несет слово w. Пусть это путь . Тогда для каждого 1 x k в ? имеется команда . Но из определения ?M следует, что тогда в автомате M имеется путь из в , несущий слово (wx). Объединив все такие пути, получим путь из из q0 в q' FM, несущий слово (w). Следовательно, (w) LM.



LM (L). Пусть слово u ?* принадлежит LM.


Покажем, что тогда для некоторого w L u =(w). Рассмотрим для этого путь в диаграмме M из q0 в q' FM, несущий слово u . Выделим на этом пути все состояния из Q. Пусть это будут по порядку состояния q0=q{j0}, q{j1}, … q{jk}= q'. Тогда слово u разбивается на k подслов: u=u1u2 … uk таких, что ux переводит в M состояние в

(1 x k). Покажем, что для каждого такого ux существует символ wx ? такой, что ux = (wx) и в ? имеется команда . Действительно, любой путь из в M начинается ?-переходом в некоторое состояние вида . Пусть это будет состояние на пути, который несет ux в . Далее этот путь обязательно будет проходить по состояниям вида и завершится ?-переходом из в состояние . Тогда из определения M следует, что ux = (ai) и в ? имеется команда . Положив wx=ai, получим, что ux = (wx) и u=(w1)(w2) … (wk) =(w), для слова w=w1w2 … wk ?*. При этом каждый символ wx этого слова переводит в автомате A состояние в . Поэтому в A существует путь из q0 в q' F, несущий слово w и, следовательно w L .

---

---