Основные свойства автоматных языков

3.2. Пересечение и дополнение автоматных языков

Теорема 3.2.1. Класс автоматных языков замкнут относительно дополнения и пересечения.

Доказательство. Если язык L распознается полным детерминированным конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$, то язык $$\Sigma ^* - L$$ распознается конечным автоматом $$\langle Q , \Sigma , \Delta , I , Q - F \rangle$$.

Пересечение выражается через объединение и дополнение (закон де Моргана).

Замечание 3.2.2. Автоматность пересечения двух автоматных языков можно легко доказать и без привлечения теоремы 2.7.1. Для этого достаточно построить по двум конечным автоматам с однобуквенными переходами$$M_1 = \langle Q_1 , \Sigma , \Delta_1 , I_1 , F_1 \rangle ,\quad M_2 = \langle Q_2 , \Sigma , \Delta_2 , I_2 , F_2 \rangle$$ новый конечный автомат$$M = \langle Q_1 \times Q_2 , \Sigma , \Delta , I_1 \times I_2 , F_1 \times F_2 \rangle ,$$ где$$\Delta = \{ \langle \langle p_1 , p_2 \rangle , a , \langle q_1 , q_2 \rangle \rangle \mid \langle p_1 , a , q_1 \rangle \in \Delta_1, \; \langle p_2 , a , q_2 \rangle \in \Delta_2 \} .$$

Упражнение 3.2.3. Обозначим через L язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a S , T \; {\to} \; a T , \\ S \; {\to} \; b S , T \; {\to} \; b T , \\ S \; {\to} \; abaa T , T \; {\to} \; \varepsilon . \\ S \; {\to} \; babb T , \end{align*}$$ Найти праволинейную грамматику, порождающую язык $$\{a,b\}^* - L$$.

Упражнение 3.2.4. Обозначим через L язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; F , M \; {\to} \; a M , F \; {\to} \; b F \\ S \; {\to} \; a a M , M \; {\to} \; b M , F \; {\to} \; ab F \\ S \; {\to} \; T , M \; {\to} \; \varepsilon , F \; {\to} \; ba F \\ T \; {\to} \; a T , F \; {\to} \; aba F \\ T \; {\to} \; b T , F \; {\to} \; aaa F \\ T \; {\to} \; a a , F \; {\to} \; \varepsilon . \end{align*}$$ Найти праволинейную грамматику, порождающую язык $$\{a,b\}^* - L$$.

Упражнение 3.2.5. Обозначим через L язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a T , T \; {\to} \; a T , C \; {\to} \; a C , \\ S \; {\to} \; b C , T \; {\to} \; b T , C \; {\to} \; b C , \\ T \; {\to} \; b , C \; {\to} \; a . \end{align*}$$ Найти праволинейную грамматику, порождающую язык $$\{a,b\}^* - L$$.

Упражнение 3.2.6. Существуют ли такие детерминированные конечные автоматы M1 и M2, что язык $$L(M_1) \cup L(M_2)$$ не порождается ни одним детерминированным конечным автоматом с количеством состояний n1n2+n1+n2, где n1 - количество состояний автомата M1 и n2 - количество состояний автомата M2?

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

Лемма 3.3.1 (pumping lemma, лемма о разрастании, лемма о накачке, лемма-насос). Пусть L автоматный язык над алфавитом $$\Sigma$$. Тогда найдется такое положительное целое число p, что для любого слова $$w \in L$$ длины не меньше p можно подобрать слова $$x , y , z \in \Sigma ^*$$, для которых верно xyz = w, $$y \neq \varepsilon$$, $$| x y | \leqslant p$$ и $$x y ^i z \in L$$ для всех $$i \geqslant 0$$.

Доказательство. Пусть язык L распознается конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$, содержащим только переходы с метками длины единица. Положим p = |Q|. Пусть слово w является меткой успешного пути$$\langle q_0 , e_1 , q_1 , e_2 , \ldots , q_n \rangle$$ и $$| w | = n \geqslant p$$. Согласно принципу Дирихле найдутся такие индексы j и k, что $$0 \leqslant j < k \leqslant p$$ и qj = qk (ведь множество индексов $$\{ 0 , 1 , \ldots , p \}$$ содержит p+1 натуральных чисел, а значения qi берутся из множества, содержащего всего p элементов). Выберем слова x, y и z так, что |x| = j, |y| = k - j и xyz = w.

Пример 3.3.2. Пусть $$\Sigma = \{ a , b \}$$. Рассмотрим автоматный язык$$L = \{ (ab)^n \mid n \geqslant 0 \ \cup \{ a (ab)^n \mid n \geqslant 0 \} .$$ Положим p = 3. Тогда для любого слова $$w \in L$$ длины не меньше p найдутся слова $$x , y , z \in \Sigma ^*$$, соответствующие утверждению леммы 3.3.1. Действительно, если w = abu для некоторого слова u, то положим $$x = \varepsilon$$, y = ab, z = u ; иначе w = aabu и можно положить x = a, y = ab, z = u.

Упражнение 3.3.3. Является ли автоматным язык$$\{ a^m b a^m \mid m \geqslant 0 \} ?$$

Упражнение 3.3.4. Является ли автоматным язык ?

Упражнение 3.3.5. Является ли автоматным язык$$\{ a^k b^m a^n \mid k \neq n \; \text{или } m = 0 \} ?$$

Упражнение 3.3.6. Является ли автоматным язык$$\{ (aab)^n a (aba)^n \mid n \geqslant 0 \} ?$$

Упражнение 3.3.7. Является ли автоматным язык$$\{ u a a v \mid u \in \{a,b\}^* ,\ v \in \{a,b\}^* ,\ | u |_b \geqslant | v |_a \} ?$$

Упражнение 3.3.8. Является ли автоматным язык$$\{ u a v \mid u \in \{a,b\}^* ,\ v \in \{a,b\}^* ,\ | u |_b \geqslant | v |_a \} ?$$

Упражнение 3.3.9. Является ли автоматным язык$$\{ a^k w b^k \mid k \geqslant 0 ,\ w \in \{a,b\}^* ,\ | w |_a \vdots 3 \} ?$$

Упражнение 3.3.10. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a S a , \\ S \; {\to} \; b S a , \\ S \; {\to} \; b S b , \\ S \; {\to} \; \varepsilon ? \end{align*}$$

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

Пример 3.4.1. Рассмотрим язык $$L = \{ a b^n a^n \mid n \geqslant 0 \}$$ над алфавитом $$\Sigma = \{ a , b \}$$. Утверждение леммы 3.3.1 не выполняется ни для какого натурального числа p. Действительно, если w = abpap, то x = abk, y = bm, z = bp-k-map для некоторых $$k \geqslant 0$$ и $$m \geqslant 1$$ или $$x = \varepsilon$$, y = abl, z = bp-lap для некоторого $$l \geqslant 0$$. В обоих случаях $$x y y z \notin L$$. Таким образом, язык L не является автоматным.

Упражнение 3.4.2. Пусть $$\Sigma = \{ a , b , c \}$$. При каких словах $$u \in \{ a , b \}^*$$ и $$v \in \{ a , b \}^*$$ язык $$\{ u^m c v^m \mid m > 0 \}$$ является автоматным?

Замечание 3.4.3. Условие, сформулированное в лемме 3.3.1, является необходимым для автоматности, но не достаточным.

Пример 3.4.4. Пусть $$\Sigma = \{ a , b \}$$. Рассмотрим язык L = {akbman | k=0 или m=n}. Положим p = 1. Тогда для любого слова $$w \in L$$ длины не меньше p найдутся слова $$x , y , z \in \Sigma ^*$$, соответствующие утверждению леммы 3.3.1. Тем не менее язык L не является автоматным, так как$$L \cap \{ a b^m a^n \mid m \geqslant 0 , \; n \geqslant 0 \} = \{ a b^n a^n \mid n \geqslant 0 \} .$$

Лемма 3.4.5*. Пусть L - автоматный язык над алфавитом $$\Sigma$$. Тогда найдется такое положительное целое число p, что для любого слова $$w \in L$$ можно подобрать слова $$x , y , z \in \Sigma ^*$$, для которых верно xyz = w, $$| y | \geqslant [ | w | / p ]$$ и $$x y ^i z \in L$$ для всех $$i \geqslant 0$$. Здесь [m] означает целую часть числа m.

Доказательство. Пусть L распознается конечным автоматом $$\langle Q , \Sigma , \Delta , I , F \rangle$$, содержащим только переходы с метками длины единица. Положим p = |Q|. Пусть слово w является меткой успешного пути $$\langle q_0 , e_1 , q_1 , e_2 , \ldots , q_n \rangle$$. Обозначим l = [|w|/p]. Если l = 0, то положим $$x = \varepsilon$$ и $$y = \varepsilon$$. Пусть $$l > 0$$. Согласно принципу Дирихле найдутся такие натуральные числа j и k, что $$0 \leqslant j < k \leqslant p$$ и qjl = qkl. Выберем слова x, y и z так, что |x| = jl, |y| = kl - jl и xyz = w.

Упражнение 3.4.6. Является ли автоматным язык$$\{ a^m b^n \mid m \neq 1 \text{ или } n \text{ простое } \} ?$$

Упражнение 3.4.7. Является ли автоматным язык$$\{ u u \reverse v \mid u \in \{a,b\}^+ ,\ v \in \{a,b\}^* \} ?$$

Упражнение 3.4.8. Является ли автоматным язык

$$\{ w \in \{a,b\}^* \mid$$ множества $$\{ x \in \{a,b\}^* \mid x a a b \sqsubset w \}$$ и $$\{ x \in \{a,b\}^* \mid x b b a \sqsubset w \}$$ равномощны?

Упражнение 3.4.9. Является ли автоматным язык

$$\{ w \in \{a,b\}^* \mid$$ множества $$\{ x \in \{a,b\}^* \mid x a a b \sqsubset w \}$$ и $$\{ x \in \{a,b\}^* \mid x b a \sqsubset w \}$$ равномощны?

Упражнение 3.4.10. Является ли автоматным язык$$\{ a^k b^n a^n \mid k \geqslant 1 ,\ n \geqslant 0 \} \cup \{ b^k a b^m a^n \mid k \geqslant 0 ,\ m \neq n \} ?$$

Упражнение 3.4.11. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} F \; {\to} \; abb , \\ F \; {\to} \; abbb F F F , \\ F \; {\to} \; abbbb F F ? \end{align*}$$