Дополнительные свойства контекстно-свободных языков

11.2. Гомоморфизмы и контекстно-свободные языки

Теорема 11.2.1. Для любого гомоморфизма $$h \colon \Sigma_1^* \farrow \Sigma_2^*$$ и контекстно-свободного языка $$L \subseteq \Sigma_1^*$$ язык h(L) является контекстно-свободным.

Доказательство. Приведем здесь доказательство, использующее МП-автоматы, хотя эту теорему легко доказать и с помощью контекстно-свободных грамматик. Пусть язык L распознается МП-автоматом $$\lalg Q , \Sigma_1 , \Gamma , \Delta , I , F \ralg$$. Тогда язык h(L) распознается МП-автоматом $$\lalg Q , \Sigma_2 , \Gamma , \Delta' , I , F \ralg$$, где$$\Delta' = \{ \lp \lp p , h ( x ) , \beta \rp , \lp q , \gamma \rp \rp \mid \lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta \} .$$

Пример 11.2.2. Пусть $$\Sigma_1 = \{ a , b , c \}$$ и $$\Sigma_2 = \{ a , b \}$$. Рассмотрим контекстно-свободный язык L, порождаемый грамматикой$$\begin{align*} S \; {\to} \; aSSc , \\ S \; {\to} \; b , \end{align*}$$ и гомоморфизм $$h \colon \Sigma_1^* \farrow \Sigma_2^*$$, заданный равенствами h(a) = a, h(b) = bba и h(c) = a. Тогда язык h(L) порождается контекстно-свободной грамматикой$$\begin{align*} S \; {\to} \; aSSa , \\ S \; {\to} \; bba , \end{align*}$$

Упражнение 11.2.3. Пусть гомоморфизм $$h \colon \{a,b,c\}^* \farrow \{a,b\}^*$$ задан соотношениями h(a) = b, $$h(b) = \varepsilon$$, h(c) = a. Рассмотрим язык L, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a , \\ S \; {\to} \; b S , \\ S \; {\to} \; c S S . \end{align*}$$ Найти контекстно-свободную грамматику для языка h(L).

Теорема 11.2.4. Для любого гомоморфизма $$h \colon \Sigma_1^* \farrow \Sigma_2^*$$ и контекстно-свободного языка $$L \subseteq \Sigma_2^*$$ язык h-1(L) является контекстно-свободным.

Доказательство. Введем обозначение$$\cala = \{ x \in \Sigma_2 ^* \mid x \suffix h ( a ) \mathspace\text{для некоторого}\mathspace a \in \Sigma_1 \} .$$ Пусть язык L распознается МП-автоматом $$\lalg Q , \Sigma_2 , \Gamma , \Delta , I , F \ralg$$. Без ограничения общности можно считать, что для каждого перехода $$\lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \in \Delta$$ выполняется неравенство $$| x | \leq 1$$. Можно проверить, что в этом случае язык h-1(L) распознается МП-автоматом $$\lalg Q' , \Sigma_1 , \Gamma , \Delta' , I' , F' \ralg$$, где$$\begin{align*} Q' = \cala \times Q ,\\ I' = \{ \varepsilon \} \times I ,\\ F' = \{ \varepsilon \} \times F ,\\ \Delta' = \{ \lp \lp \lp \varepsilon , p \rp , a , \varepsilon \rp , \lp \lp h ( a ) , p \rp , \varepsilon \rp \rp \mid a \in \Sigma_1 \commaand p \in Q \} \cup {} \\ \myqquad \cup \{ \lp \lp \lp x w , p \rp , \varepsilon , \beta \rp , \lp \lp w , q \rp , \gamma \rp \rp \squeeze{\mid} \lp \lp p , x , \beta \rp , \lp q , \gamma \rp \rp \squeeze{\in} \Delta \commaand x w \squeeze{\in} \cala \} . \end{align*}$$

Пример 11.2.5. Пусть $$\Sigma_1 = \{ c , d , e \}$$ и $$\Sigma_2 = \{ a , b \}$$. Рассмотрим гомоморфизм $$h \colon \Sigma_1^* \farrow \Sigma_2^*$$, заданный равенствами h(c) = aa, h(d) = b и h(e) = bba. Пусть контекстно-свободный язык L распознается МП-автоматом $$\lalg Q , \Sigma_2 , \Gamma , \Delta , I , F \ralg$$, где Q = {p}, $$\Gamma = \{ A \}$$, I = {p}, F = {p},$$\Delta = \{ \lp \lp p , a , \varepsilon \rp , \lp p , A \rp \rp ,\ \lp \lp p , b , A \rp , \lp p , \varepsilon \rp \rp \} .$$ $$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F=]{p} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{0,-1} ^{b,A:\varepsilon} }$$ Тогда язык h-1(L) распознается МП-автоматом $$\lalg Q' , \Sigma_1 , \Gamma , \Delta' , I' , F' \ralg$$, где $$Q' = \{ p_{\varepsilon} , p_{a} , p_{aa} , p_{b} , p_{ba} , p_{bba} \}$$, $$I' = \{ p_{\varepsilon} \}$$, $$F' = \{ p_{\varepsilon} \}$$ и$$\begin{align*} \Delta' = \{ \lp \lp p_{\varepsilon} , c , \varepsilon \rp , \lp p_{aa} , \varepsilon \rp \rp ,\ \lp \lp p_{\varepsilon} , d , \varepsilon \rp , \lp p_{b} , \varepsilon \rp \rp ,\ \lp \lp p_{\varepsilon} , e , \varepsilon \rp , \lp p_{bba} , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp p_{a} , \varepsilon , \varepsilon \rp , \lp p_{\varepsilon} , A \rp \rp ,\ \lp \lp p_{aa} , \varepsilon , \varepsilon \rp , \lp p_{a} , A \rp \rp ,\ \lp \lp p_{b} , \varepsilon , A \rp , \lp p_{\varepsilon} , \varepsilon \rp \rp ,\ \\ \hphantom{ {} = {} \{ } %\} \lp \lp p_{ba} , \varepsilon , A \rp , \lp p_{a} , \varepsilon \rp \rp ,\ \lp \lp p_{bba} , \varepsilon , A \rp , \lp p_{ba} , \varepsilon \rp \rp \} . \end{align*}$$ $$\objectwidth={7.5mm} \objectheight={7.5mm} \let\objectstyle=\scriptstyle \xymatrix @=11mm{ % *=[o][F-]{p_{aa}} \ar "1,3" ^{\varepsilon,\varepsilon:A} *=[o][F-]{p_{a}} \ar "2,4" _{\varepsilon,\varepsilon:A} \\ *=[o][F-]{p_{bba}} \ar "2,2" ^{\varepsilon,A:\varepsilon} *=[o][F-]{p_{ba}} \ar "1,3" _{\varepsilon,A:\varepsilon} *=[o][F=]{p_{\varepsilon}} \ar @`{+/l16mm/} [] ^{} \ar `u^l{[-1,-2]+/u9mm/}_{c}`l^d{[-1,-2]} "1,2" \ar `d_l{[1,-1]}^-{d} "3,3" \ar `r_d{+/r7mm/}`d_l{[1,-1]+/d7mm/}^{e}`l_u{[0,-3]} "2,1" \\ % *=[o][F-]{p_{b}} \ar "2,4" ^{\varepsilon,A:\varepsilon} }$$

Язык h-1(L) также порождается контекстно-свободной грамматикой $$\begin{align*} S \; {\to} \; \varepsilon , T \; {\to} \; \varepsilon , \\ S \; {\to} \; cTUdS , T \; {\to} \; cTUU ,\\ U \; {\to} \; dT , \\ U \; {\to} \; eT . \end{align*} $$

Упражнение 11.2.6. Пусть гомоморфизм $$h \colon \{a,b,c\}^* \farrow \{a,b\}^*$$ задан соотношениями h(a) = ab, h(b) = aaba, h(c) = b. Рассмотрим язык L, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a S , \\ S \; {\to} \; a S b S , \\ S \; {\to} \; b S a S . \end{align*}$$ Описать язык h-1(L).

Упражнение 11.2.7. $$h \colon \{c,d,e\}^* \farrow \{a,b\}^*$$ задан соотношениями h(c) = a, h(d) = ba, h(e) = bb. Рассмотрим язык L, порождаемый грамматикой$$\begin{align*} B \; {\to} \; a B B a , \\ B \; {\to} \; b . \end{align*}$$ Найти контекстно-свободную грамматику для языка h-1(L).

Упражнение 11.2.8. Пусть гомоморфизм $$h \colon \{c,d,e\}^* \farrow \{a,b\}^*$$ задан соотношениями $$h(c) = bba$$, $$h(d) = aa$$, $$h(e) = b$$. Рассмотрим язык $$L$$, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a S b S , \\ S \; {\to} \; \varepsilon . \end{align*}$$ Найти контекстно-свободную грамматику для языка h-1(L).

Упражнение 11.2.9. Обозначим через L язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a S b , \\ S \; {\to} \; ba . \end{align*}$$ Рассмотрим гомоморфизм $$h_1 \colon \{a,b,c,d,e,f\}^* \farrow \{a,b,c\}^*$$, заданный соотношениями

h1(a) = ac ,
 h1(b) = bc ,
 h1(c) = aa ,
 h1(d) = ab ,
 h1(e) = ba ,
 h1(f) = bb ,

и гомоморфизм $$h_2 \colon \{a,b,c,d,e,f\}^* \farrow \{a,b\}^*$$, заданный соотношениями

h2(a) = a ,
 h2(b) = b ,
 h2(c) = ab ,
 h2(d) = aa ,
 h2(e) = bb ,
 h2(f) = ba .

Найти контекстно-свободную грамматику, порождающую язык$$h_2(h_1^{-1}( L \cdot \{ \varepsilon , c \} )) .$$

11.3. Представления контекстно-свободных языков посредством гомоморфизмов

Теорема 11.3.1. Рассмотрим алфавит $$\Sigma_0 = \{ a_1 , a_2 , b_1 , b_2 , c \}$$ и язык $$L_0 \subseteq \Sigma_0^*$$, порождаемый контекстно-свободной грамматикой G0:$$\begin{align*} S \; {\to} \; C b_1 b_2 b_1 R C , A \; {\to} \; a_1 , R \; {\to} \; \varepsilon , \\ C \; {\to} \; c , A \; {\to} \; a_2 , R \; {\to} \; T a_1 T b_1 , \\ C \; {\to} \; c D C , A \; {\to} \; b_1 , R \; {\to} \; T a_2 T b_2 , \\ D \; {\to} \; A , A \; {\to} \; b_2 , T \; {\to} \; R , \\ D \; {\to} \; A D , T \; {\to} \; R C C . \end{align*}$$ Произвольный язык $$L \subseteq \Sigma^*$$ является контекстно-свободным тогда и только тогда, когда существует такой гомоморфизм $$h \colon \Sigma^* \farrow \Sigma_0^*$$, что L = h-1(L0) или $$L = h^{-1} ( L_0 \cup \{ \varepsilon \} )$$.

Доказательство. Достаточность следует из теоремы 11.2.4. Приведем теперь идею доказательства необходимости (полное доказательство можно найти в [Сал, с. 103-109]).

Пусть дан произвольный контекстно-свободный язык L. Согласно теореме 8.4.6 язык $$L \sminus \{ \varepsilon \}$$ порождается некоторой контекстно-свободной грамматикой $$\lalg \{ A_1 , \ldots , A_n \} , \Sigma , P , A_1 \ralg$$, в которой каждое правило имеет один из следующих трех видов: $$A_i \tto a$$, $$A_i \tto a A_j$$, $$A_i \tto a A_j A_k$$, где $$a \in \Sigma$$.

Определим вспомогательную функцию $$\bar{h}$$, ставящую в соответствие каждому символу из $$\Sigma$$ конечный язык над алфавитом $$\Sigma_0$$ следующим образом:$$\begin{align*} \bar{h} ( a ) = \{ b_1 b_2^i b_1 \mid ( A_i \tto a ) \in P \} \cup {} \\ \qquad \cup \{ b_1 b_2^i b_1 a_1 a_2^j a_1 \mid ( A_i \tto a A_j ) \in P \} \cup {} \\ \qquad \cup \{ b_1 b_2^i b_1 a_1 a_2^k a_1 a_1 a_2^j a_1 \mid ( A_i \tto a A_j A_k ) \in P \} . \end{align*}$$ Искомый гомоморфизм h определяется следующим образом: если$$\bar{h} ( a ) = \{ w_1 , w_2 , \ldots , w_k \} ,$$ положим$$h ( a ) = c w_1 c w_2 c \ldots c w_k c .$$

Пример 11.3.2. Пусть $$\Sigma = \{ d , f , g \}$$. Рассмотрим язык L, порождаемый грамматикой$$\begin{align*} A_1 \; {\to} \; f , \\ A_1 \; {\to} \; d A_1 A_2 , \\ A_2 \; {\to} \; f A_3 , \\ A_2 \; {\to} \; f A_2 A_3 , \\ A_3 \; {\to} \; g . \end{align*}$$ Тогда L = h-1(L0), где гомоморфизм h задан равенствами

h(d) = cb1b2b1a1a2a2a1a1a2a1c,
h(f) = cb1b2b1cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c,
h(g) = cb1b2b2b2b1c.

Рассмотрим, например, слово $$d {} f f g \in L$$. Проверим, что слово h(dffg) выводится в грамматике G0 из теоремы 11.3.1. Очевидно, что $$S \overstar{\Rightarrow} c b_1 b_2 b_1 R c$$. С помощью последних пяти правил грамматики G0 можно вывести, что$$R \mymathrel{\overstar{\Rightarrow}} a_1 a_2 a_2 a_1 a_1 a_2 a_1 C C b_1 b_2 b_1 C C b_1 b_2 b_2 b_1 a_1 a_2 a_2 a_2 a_1 C C b_1 b_2 b_2 b_2 b_1 .$$ Осталось найти такие шесть выводимых из C слов $$w_1 , \ldots , w_6$$, что$$\begin{multiline*} h ( d {} f f g ) = \\= c b_1 b_2 b_1 % a_1 a_2^2 a_1^2 a_2 a_1 w_1 w_2 b_1 b_2 b_1 w_3 w_4 a_1 a_2^2 a_1 a_1 a_2 a_1 w_1 w_2 b_1 b_2 b_1 w_3 w_4 b_1 b_2^2 b_1 a_1 a_2^3 a_1 w_5 w_6 b_1 b_2^3 b_1 c . \end{multiline*}$$ Подходят слова

w1 = c,
w2 = c,
w3 = cb1b2b2b1a1a2a2a2a1cb1b2b2b1a1a2a2a2a1a1a2a2a1c,
w4 = cb1b2b1c,
w5 = cb1b2b2b1a1a2a2a2a1a1a2a2a1c,
w6 = c.

Теорема 11.3.3 (Теорема Хомского-Шютценберже). Язык $$L \subseteq \Sigma^*$$ является контекстно-свободным тогда и только тогда, когда существуют такие натуральное число n, автоматный язык L1 над алфавитом $$\Sigma_n^{(\textup{D})} = \{ a_1 , b_1 , a_2 , b_2 , \ldots , a_n , b_n \}$$ и гомоморфизм $$h \colon \bigl(\Sigma_n^{(\textup{D})}\bigr)^* \farrow \Sigma ^*$$, что $$L = h ( L_n^{(\textup{D})} \cap L_1 )$$, где $$L_n^{(\textup{D})}$$ - язык Дика над 2n буквами.

Доказательство можно найти в [Лал, с. 331-333].

Упражнение 11.3.4. Рассмотрим язык L1, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a S b S , \\ S \; {\to} \; \varepsilon , \end{align*}$$ и язык L2, порождаемый грамматикой$$\begin{align*} S \; {\to} \; bb S a , \\ S \; {\to} \; \varepsilon . \end{align*}$$ Найти такой гомоморфизм $$h \colon \{a,b\}^* \farrow \{a,b\}^*$$, что$$h(L_1 \cap \{ a^m b^n \mid m \geq 0 ,\ n \geq 0 \}) = L_2 .$$