Свойства замкнутости класса автоматных языков. Неавтоматные языки

Пример 6.2. Пусть алфавиты $$\Sigma,$$ $$\Delta$$ и гомоморфизм $$\phi$$ определены как выше в примере 6.1. Рассмотрим язык L={ w | число букв а в слове w нечетно }.

На следующем рисунке показана диаграмма ДКА A, распознающего язык L, и диаграммы автоматов Ma для $$\varphi (a) =00$$, Mb для $$\varphi (b) =\varepsilon$$ и Mc для $$\varphi (c) =101$$.

Подставив в A вместо a -переходов автомат Ma, вместо b -переходов автомат Mb и вместо c -переходов автомат Mc, получим представленный на рис. 6.2 недетерминированный автомат M, распознающий язык $$\varphi (L)$$. На этом рисунке каждая из $$\varepsilon$$ -петель в состояниях q0 и q1 заменяет по три $$\varepsilon$$ -перехода, связанных с Mb.

Отметим, что конструкция автомата M в теореме 6.1 удобна для доказательства, но несколько избыточна. Без труда можно сократить в ней все $$\varepsilon$$ -переходы, склеив начальные и заключительные состояния автоматов Mi с соответствующими состояниями автомата A. Например, в автомате на рис. 6.2 можно объединить начальные состояния p00 и p001 с q0, заключительные состояния p201 и p313 с q1 и т.п.

Одним из интересных частных случаев гомоморфизма является проекция.

Определение 6.3. Пусть $$\Delta \subset \Sigma$$. Проекцией языка L в алфавите $$\Sigma$$ на подалфавит $$\Delta$$ называется язык $$PROJ_{\Delta }(L) = \{ w | w$$ получено из некоторого слова $$v\in L$$ вычеркиванием всех символов, не принадлежащих алфавиту $$\Delta \}$$.

Определим гомоморфизм $$\pi : \Sigma ^{*} \to \Delta ^{*}$$ следующим образом: $$\pi (a)=a$$, если $$a \in \Delta$$ и $$\pi (a)=\varepsilon$$, если $$a \notin \Delta$$. Тогда для всякого языка L в алфавите $$\Sigma$$ имеет место равенство $$PROJ_{\Delta } (L) = \pi (L)$$. Отсюда и из предыдущей теоремы 6.1 получаем замкнутость класса автоматных языков относительно проекции.

Предложение 6.2. Для любых алфавитов $$\Delta$$ и $$\Sigma$$ таких, что $$\Delta \subset \Sigma$$, и любого автоматного языка L в алфавите $$\Sigma$$ проекция $$PROJ_{\Delta }(L)$$ также является автоматным языком.

Отметим, что для проекции конструкция автомата M для $$PROJ_{\Delta } (L)$$ по ДКА A для L существенно упрощается: достаточно в A все переходы по символам из $$\Sigma \setminus \Delta$$ заменить на $$\varepsilon$$ -переходы.

Следующая теорема устанавливает замкнутость класса автоматных языков относительного обращения гомоморфизмов.

Теорема 6.2. Пусть $$\varphi : \Sigma ^{*} \to \Delta ^{*}$$ - произвольный гомоморфизм и L - автоматный язык в алфавите $$\Delta.$$ Тогда и язык $$\varphi ^{-1}(L)$$ является автоматным.

Доказательство Пусть $$A=<\Delta , Q, q_{0}, F, \Phi >$$ - ДКА, распознающий язык L. Пусть $$\Sigma = \{ a_{1}, \dots , a_{m}\}$$, Q= {q0, q1, ..., qn} и $$\varphi (a_{i})= d_{1}^{i}d_{2}^{i} \dots d_{\{ }k_{i}\} ^{i}, d_{l}^{i} \in \Delta (1\le l \le k_{i})$$ (если $$\varphi (a_{i}) \ne \varepsilon$$ ).

Перестроим его в ДКА $$M =<\Sigma , Q, q_{0}, F, \Phi ^{M}>$$ с тем же множеством состояний, начальным и заключительными состояниями, который распознает язык $$\varphi ^{-1}(L)$$.

Идея этого построения состоит в том, чтобы переходить из состояния q в q' по букве $$a\in \Sigma$$ в автомате M, если в автомате A слово $$\varphi (a) \ne \varepsilon$$ переводит q в q'. Если же для $$a\in \Sigma$$ образ пуст, т.е. $$\varphi (a) = \varepsilon$$, то в автомате M слово a переводит каждое состояние в себя, так как символы a могут встречаться в каждом слове из $$\varphi ^{-1}(L)$$ в любом месте и в любом количестве.

Таким образом, положим для каждой пары $$q_{j} \in Q$$ и $$a_{i}\in \Sigma$$ $$\Phi ^{M}(q_{j}, a_{i}) = q_{r}$$, если $$\varphi (a_{i}) \ne \varepsilon$$ и в автомате A $$(q,\phi(a))\vdash_A^* (q_r, \varepsilon)$$. Если же $$\varphi (a_{i}) = \varepsilon$$, то полагаем $$\Phi ^{M}(q_{j}, a_{i}) = q_{j}$$.

Так как A - детерминированный автомат, то функция переходов $$\Phi ^{M}$$ определена однозначно и для всех пар $$q_{j} \in Q$$ и $$a_{i}\in \Sigma$$. Следовательно, M детерминированный.

Нетрудно показать, что $$L_{M} = \varphi ^{-1}(L)$$.

Действительно, если слово $$w=a_{i_1}a_{i_2}\ldots a_{i_k}\ \in L_M$$, то в M путь $$q_0, q_{i_1}q_{i_2}\ldots q_{i_k}$$, несущий это слово ведет в заключительное состояние $$q_{i_k}\in F$$. Из определения $$\Phi ^{M}$$ следует, что тогда в A существует соответствующий путь из q0 в $$q_{i_k}\in F$$, который несет слово $$\phi(a_{i_1})\phi(a_{i_2})\ldots \phi(a_{i_k}) = \phi(w)$$. Следовательно, $$w \in \varphi ^{-1}(L)$$.

Обратно, пусть $$w=a_{i_1}a_{i_2}\ldots a_{i_k}\ \in \phi^{-1}(L)$$. Тогда слово $$u = \phi(w) = \phi(a_{i_1})\phi(a_{i_2})\ldots \phi(a_{i_k}) \in L$$ и в автомате A имеется путь, несущий u, который переводит q0 в некоторое заключительное состояние $$q' \in F$$. Зафиксируем на этом пути состояния $$q_{i_j}$$, в которые он попадает после прочтения префиксов $$\phi(a_{i_1})\phi(a_{i_2})\ldots \phi(a_{i_j})$$ слова u (j = 1, 2, ... , k). Тогда $$q_{i_k} = q^\prime$$ и для всех j = 1, 2, ... , k имеет место $$\ (q_{i_{j-1}},\phi(a_{i_j})\ \vdash_A^*\ (q_{i_j}, \varepsilon)$$. Отсюда и из определения $$\Phi ^{M}$$ получаем, что в M для всех j = 1, 2, ... , k имеет место переход ха один шаг $$\ q_{i_{j-1}},a_{i_j} \rightarrow q_{i_j}$$. Следовательно, в M путь q0, q{i1}q{i2}... q{ik} несет слово w и завершается в заключительном состоянии $$q_{i_k} = q^\prime$$. А это означает, что $$w \in L_{M}$$.

Пример 6.3. Пусть алфавиты $$\Sigma,$$ $$\Delta$$ и гомоморфизм $$\phi$$ определены как выше в примере: $$\varphi (a) =00, \varphi (b) =\varepsilon , \varphi (c) =101$$. Рассмотрим язык L={ w | число букв 0 в слове w нечетно, а число букв 1 - четно}.

На следующем рисунке показана диаграмма ДКА A, распознающего язык L.

Применив к этому автомату конструкцию из теоремы 6.2, обнаружим, что a и b оставляют все состояния на месте, а c переводит каждое состояние в соседнее состояние "по горизонтали". В результате получаем автомат M, показанный ниже на рис. 6.4.

Легко заметить, что в нем состояния q2 и q3 недостижимы из начального состояния q0 и что этот автомат M распознает язык

Имеется еще много операций, относительно которых замкнут класс автоматных языков. Некоторые из них приведены далее в разделе задач.

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

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

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

Пусть L - бесконечный автоматный язык. Тогда существует такая константа n, что любое слово $$w \in L$$ длины |w| > n можно разбить на три части x, y и z так, что w = xyz и

(Здесь $$y^{0}= \varepsilon , y^{1}=y, y^{i+1} = y^{i}y$$ ).

Доказательство Так как язык L автоматный, то существует ДКА $$A=<\Sigma , Q, q_{0}, F, \Phi >$$, распознающий L. Пусть |Q|= n и слово $$w=w_{1}w_{2} \dots w_{k} \in L$$ имеет длину k > n. Рассмотрим путь $$p=(q_0=q_{i_0},q_{i_1}, \ldots , q_{i_k})$$ в диаграмме A, который несет слово w. Очевидно, что среди первых (n+1) состояний этого пути хотя бы одно встречается дважды. Выберем первое из таких состояний $$q \in Q$$. Тогда для некоторой пары чисел l < j <= n имеем $$q_{i_l} =q_{i_j}= q$$. Пусть x=w1w2 ... wl - это префикс w, который переводит q0 в $$q_{i_l}=q$$, $$y=w_{i+1}\ldots w_j$$ - это подслово w, которое переводит $$q_{i_l}=q$$ в $$q_{i_j}= q$$, и $$z = w_{j+1}\ldots w_k$$ - это суффикс w, который переводит $$q_{i_j}= q$$ в $$q_{i_k} \in F$$. x и z могут быть пусты, но |y| = j-l >= 1. Длина |xy| = j <= n. Таким образом, условия (1) и (2) теоремы выполнены. Нетрудно убедиться и в выполнении условия (3). Действительно, выбросив из пути p цикл $$q_{i_l}=q, \ldots , q_{i_j}$$, получим путь p0 из q0 в $$q_{i_k}\in F$$, который несет слово xz, а повторив этот цикл m раз, получим путь p0 из q0 в $$q_{\{ }i_{k}\} \in F$$, который несет слово xym z. Следовательно, для любого m >= 0 $$w_{m} = x y^{m} z \in L$$.

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

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

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

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

Пример 6.4. Покажем, что язык L1 ={ w =0i 1i | i >= 1 } не является автоматным.

Предположим, что он автоматный. Тогда для него имеется n из утверждения теоремы 6.3. Рассмотрим следующее ("специальное" !) слово w = 0n 1n. Очевидно, что $$w \in L_{1}$$. Предположим, что существует разбиение w = xyz, удовлетворяющего условиям (1) и (2) теоремы. Так как по условию (2) |xy| <= n, то y = 0i для некоторого i>0. Но тогда слово $$w_{0} = xz= 0^{n-i}1^{n} \notin L_{1}$$, что противоречит условию (3) теоремы. Следовательно язык L1 не автоматный.

Пример 6.5. Покажем, что язык СКОБ правильных скобочных последовательностей в алфавите { (, ) } не является автоматным.

Схема доказательства та же. В качестве специального слова выберем слово w = (n )n, оно, очевидно, принадлежит СКОБ. Тогда для всякого разбиения w = xyz такого, что |xy| <= n слово y = (i для некоторого i>0. И, как и в предыдущем примере, слово $$w_{0} = xz= (^{n-i})^{n} \notin СКОБ$$, что противоречит условию (3) теоремы. Следовательно, язык СКОБ не автоматный.

Пример 6.6. Покажем, что язык L2 ={ w =0i 1j | i <= 2j+1 } не является автоматным.

Здесь, предположив, что L2 автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово $$w = 0^{\{ }2n+1\} 1^{n} \in L_{2}$$. Для всякого разбиения w = xyz такого, что |xy| <= n слово y = 0i для некоторого i>0. Рассмотрим слово w2 = x y2 z = 0{2n+1+i}1n. Но $$2n+1+i \geq 2n+2 \not\leq 2n+1$$. Следовательно, $$w_{2} \notin L_{2}$$ и язык L2 не является автоматным.

Пример 6.7. Рассмотрим язык "квадратов" в унарном алфавите { | }:

Здесь, предположив, что L3 автоматный язык и зафиксировав константу n из теоремы 6.3, рассмотрим слово w = |{n2}. Для всякого разбиения w = xyz такого, что |xy| <= n слово y = |i для некоторого 0 < i <= n. Тогда $$w_0= xz = |^{n^2 - i}$$. Но n2 - i >= n2 -n > n2 -2n +1 =(n-1)2. Следовательно, n2 - i не является полным квадратом и $$w_{0} \notin L_{3}$$, т.е. язык "квадратов" 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' - составное число и $$w_{k} \notin L_{pr}$$. Следовательно, Lpr - не автоматный язык. Заметим, что в этом примере k выбирается для каждого n по-своему.

Еще один прием доказательства неавтоматности языка L состоит в том, чтобы вместо L рассмотреть некоторый язык L' = op(L,L1,... , Lk), полученный из L и автоматных языков L1,... , Lk с помощью операций op, сохраняющих автоматность. Если доказать, что L' не является автоматным, то и исходный язык L не автоматен.

Пример 6.9. Рассмотрим язык $$L_{4} =\{ 0^{i} 1^{j} | i \ne j \}$$.

Пусть L5= {0i1j | i >= 1, j >= 1}. Очевидно, что язык L5 автоматный. Нетрудно заметить, что его пересечение с дополнением L4 совпадает с языком L1 из примера 6.4, т.е. $$L_{1} = L_{5} \cap o\verline\{ L_{4}\}$$. Так как мы установили, что L1 не автоматный, то и L4 не является автоматным.

Являются ли условия теоремы 6.3 достаточными для того, чтобы язык оказался автоматным? Следующий пример показывает, что ответ на этот вопрос отрицателен.

Пример 6.10.Пусть L6 ={cr ai bi | r >= 1 , i>= 0 }, L7= { aibj | i >= 0, j >= 0}. Рассмотрим язык $$L_{8} = L_{6} \cup L_{7}$$.

Для этого языка можно в качестве n выбрать 1. Каждое слово w из L8 принадлежит L6 или L7. Если слово $$w= c^{r} a^{i} b^{i} \in L_{6}$$, то оно представимо в виде xyz, где $$x=\varepsilon , y=c, z= c^{r-1} a^{i} b^{i} ( r \ge 1, i \ge 0 )$$. Тогда w0 = z= cr-1 ai bi ( r >= 1, i >= 1 ) и при r=1 слово $$w_{0} = a^{i} b^{i} \in L_{7}$$, а при r > 1, очевидно, $$w_{0} \in L_{6}$$. При k >= 1 имеем $$w_{k} =c^{r+k-1} a^{i} b^{i} \in L_{6}$$. Если слово $$w= a^{i} b^{j} \in L_{7}$$ и i >= 1, то его можно представить как в виде xyz, где $$x=\varepsilon , y=a, z= a^{i-1} b^{j} ( i \ge 1, j \ge 0 )$$ и для каждого k>= 0 $$w_{k} = a^{k}a^{ i-1} b^{j} \in L_{7}$$. Если же i =0, то w= bj ( j >= 1 ) и его можно разбить на части $$x=\varepsilon , y=b, z= b^{j-1} ( j \ge 1 )$$. И в этом случае для каждого k >= 0 $$w_{k} =b^{k} b^{j-1} \in L_{7}$$. Во всех случаях $$w_{k} \in L_{8}$$ и, следовательно язык L8 удовлетворяет условиям теоремы 6.3. Но этот язык не автоматный. Действительно, пусть $$\varphi : \{ a, b, c\} ^{*} \to \{ 0, 1 \} ^{*}$$ - это гомоморфизм, заданный как $$\varphi (a)=0, \varphi (b) = 1, \varphi (c) =\varepsilon$$. Тогда $$\varphi (L_{8} \setminus L_{7}) = \varphi (L_{6}) = L_{1}$$ из примера 6.4. Так как язык L7 является автоматным, а L1 - нет, то и язык L8 не является автоматным.

Задачи

Задача 6.1. Примените процедуру детерминизации из теоремы 4.2 и постройте ДКА, эквивалентный построенному выше в примере 6.2 НКА M.

Задача 6.2. Цилиндрификация - это операция, которая обратна проекции. Для любых алфавитов $$\Delta$$ и $$\Sigma$$ таких, что $$\Delta \subset \Sigma$$, и любого языка L в алфавите $$\Delta$$ определим его цилиндрификацию как язык $$CYL_{\Sigma }(L) = \{ w \in \Sigma ^{*} | при \ вычеркивании \ из \ w \ всех \ букв, \ не \ входящих \ в \Delta , \ получается \ слово \ u \in L)$$.

Показать, что для автоматного языка L язык $$CYL_{\Sigma }(L)$$ также является автоматным языком. Предложите процедуру перестройки автомата, распознающего L , в автомат, распознающий $$CYL_{\Sigma }(L)$$.

Задача 6.3. Обращением слова $$w=w_{1}w_{2} \dots w_{k} (w_{i} \in \Sigma , i=1, \dots , k)$$ называется слово w{-1}= wk ... w2 w1. Показать, что для автоматного языка L его обращение - язык $$L^{\{ }-1\} =\{ w^{\{ }-1\} | w \in L\}$$ также является автоматным языком.

Задача 6.4. Пусть L - автоматный язык в алфавите $$\Sigma.$$ Доказать, что автоматными являются и следующие языки:

Задача 6.5. Пусть L - автоматный язык в алфавите $$\Sigma =\{ a_{1},\dots , a_{m}\}$$, а L1,..., Lm - это автоматные языки в алфавите $$\Delta.$$ Доказать, что автоматным является и язык ЗАМ(L), полученный из слов L заменой каждой буквы ai на некоторое слово из Li, т.е. $$ЗАМ(L) = \{ w | textit\{ \ существует \ такое \ слово \} u=a_{\{ }i_{1}\} a_{\{ }i_{2}\} \dots a_{\{ }i_{n}\} \in L$$ и такие слова $$w_{1},w_{2},\dots , w_{n} \in \Delta ^{*}$$, что $$w=w_{1}w_{2}\dots w_{n} и w_{j} \in L_{\{ }i_{j}\}$$ для всех j=1,2,... n }.

Задача 6.6. Пусть L - автоматный язык в алфавите $$\Sigma,$$ k - целое положительное число и $$\phi$$ - отображение $$\Sigma ^{k}$$ в $$\Sigma.$$ Доказать, что автоматным является язык $$L_{1} =\{ \varphi (a_{1}a_{2}\dots a_{k}) \dots \varphi (a_{\{ }(n-1)k+1\} a_{(n-1)k+2} \dots a_{nk}) | a_{1}a_{2}\dots a_{nk} \in L\}$$.

Задача 6.7. Докажите, что теорема 6.3 о разрастании остается справедливой и при замене условия 1) |xy| <= n на условие 1') |yz| <= n, т.е. повторяющееся подслово y имеется и в суффиксе w длины <= n.

Задача 6.8. Доказать, что следующие языки в алфавите $$\Sigma =\{ a, b, c\}$$ не являются автоматными.

Задача 6.9. $$\lambda$$ -выражение - это либо переменная x, или символ $$\lambda,$$ за которым следует переменная, а далее либо $$\lambda$$ -выражение, либо левая скобка, $$\lambda$$ -выражение, еще одно $$\lambda$$ -выражение и правая скобка. Например, $$\lambda x x, \lambda x(x x), \lambda x \lambda x (\lambda x(x x) \lambda x(x x))$$ - это правильные $$\lambda$$ -выражения, а $$(x x), \lambda x(\lambda x)$$ и $$\lambda x((x x)$$ - неправильные. Докажите, что язык $$\lambda$$ -выражений в алфавите $$\{ x, \lambda , (, ) \}$$ не является автоматным.

Задача 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 \ne \ число \ букв \ b \ в \ w \}$$ в алфавите $$\Sigma =\{ a, b\}$$ не является автоматным.