В этой лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Всюду предполагается, что в индивидуальных задачах каждый язык представлен контекстно-свободной грамматикой (но можно, конечно, использовать и автоматы с магазинной памятью).
В разделе 16.1
доказывается неразрешимость
проблемы пустоты пересечения
В разделе 16.2
доказывается неразрешимость
проблемы однозначности
В разделе 16.3
доказывается неразрешимость
проблемы равенства
В разделе 16.4
доказывается неразрешимость
проблемы
автоматности
В разделе 16.5
доказывается неразрешимость
проблем
контекстной свободности дополнения
Определение 16.1.1.
Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$.
Пусть $$\vec x = ( x_1 , \ldots , x_n ) $$,
где $$x_i \in \{ a , b \}^* $$
для всех i.
Обозначим через $$G ( \vec x ) $$
линейную грамматику $$\lalg \{ S \} , \Sigma_3 , P , S \ralg $$,
где$$P = \{ S \tto b a^i S x_i \mid 1 \leq i \leq n \} \cup
\{ S \tto b a^i c x_i \mid 1 \leq i \leq n \} .$$
Обозначим через $$\pcpl{\vec x} $$
язык, порождаемый грамматикой $$G ( \vec x ) $$.
Лемма 16.1.2. Язык $$\pcpl{\vec x} \cap \pcpl{\vec y} $$ является непустым тогда и только тогда, когда постовская система соответствия $$( \vec x , \vec y ) $$ имеет решение.
Пример 16.1.3.
Рассмотрим постовскую систему соответствия$$\domino{ b }{ bba } ,
\domino{ abbaa }{ a }$$
(то есть n = 2, $$\vec x = ( b , abbaa ) $$
и $$\vec y = ( bba , a ) $$ ).
Решениями этой системы являются последовательности (1, 1, 2), (1, 1, 2, 1, 1, 2)
и т. д.
Легко убедиться, что$$\pcpl{\vec x} \cap \pcpl{\vec y} =
\{ (baababa)^n c (bbabbaa)^n \mid n \geq 1 \} .$$
Теорема 16.1.4. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, верно ли, что $$L(G_1) \cap L(G_2) = \varnothing $$.
Доказательство. Сначала докажем утверждение теоремы для случая $$| \Sigma | \geq 3 $$. Из леммы 16.1.2 следует, что если бы проблема распознавания свойства $$L(G_1) \cap L(G_2) = \varnothing $$ для контекстно-свободных грамматик над алфавитом $$\Sigma $$ была разрешима, то проблема соответствий Поста тоже была бы разрешима. Поэтому из неразрешимости проблемы соответствий Поста следует неразрешимость проблемы распознавания свойства $$L(G_1) \cap L(G_2) = \varnothing $$ для контекстно-свободных грамматик над алфавитом $$\Sigma $$.
Чтобы доказать утверждение теоремы для случая $$| \Sigma | = 2 $$
(например, $$\Sigma = \{ d , e \} $$ ),
достаточно заменить в определении $$G (\vec x) $$
символ a на ede,
символ b на edde
и символ c на eddde.
Лемма 16.1.5. Язык $$\pcpl{\vec x} \cap \pcpl{\vec y} $$ является бесконечным тогда и только тогда, когда постовская система соответствия $$( \vec x , \vec y ) $$ имеет решение.
Доказательство. Если постовская система соответствия имеет хотя бы одно решение, то она имеет бесконечно много решений.
Теорема 16.1.6. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, является ли бесконечным язык $$L(G_1) \cap L(G_2) $$.
Упражнение 16.1.7.
Пусть $$\Sigma = \{ a, b, c, d_1, d_2, d_3 \} $$.
Рассмотрим язык L1,
порождаемый грамматикой$$\begin{align*}
F \; {\to} \; d_1 F a , \\
F \; {\to} \; d_2 F aab , \\
F \; {\to} \; d_3 F baa , \\
F \; {\to} \; c ,
\end{align*}$$
и язык L2,
порождаемый грамматикой$$\begin{align*}
J \; {\to} \; d_1 J aa , \\
J \; {\to} \; d_2 J bb , \\
J \; {\to} \; d_3 J a , \\
J \; {\to} \; c .
\end{align*}$$
Верно ли, что $$L_1 \cap L_2 = \{ c \} $$?
Упражнение 16.1.8.
Пусть $$\Sigma = \{ a, b, c, d_1, d_2, d_3 \} $$.
Рассмотрим язык L1,
порождаемый грамматикой$$\begin{align*}
F \; {\to} \; d_1 F b , F \; {\to} \; d_1 c b , \\
F \; {\to} \; d_2 F a , F \; {\to} \; d_2 c a , \\
F \; {\to} \; d_3 F aba , F \; {\to} \; d_3 c aba ,
\end{align*}$$
и язык $$L_2 $$,
порождаемый грамматикой$$\begin{align*}
J \; {\to} \; d_1 J , J \; {\to} \; d_1 c , \\
J \; {\to} \; d_2 J aa , J \; {\to} \; d_2 c aa , \\
J \; {\to} \; d_3 J b , J \; {\to} \; d_3 c b .
\end{align*}$$
Верно ли, что $$L_1 \cap L_2 = \varnothing $$?
Упражнение 16.1.9.
Пусть $$\Sigma = \{ a, b, c \} $$.
Рассмотрим язык L1,
порождаемый грамматикой$$\begin{align*}
F \; {\to} \; ba F a , F \; {\to} \; ba c a , \\
F \; {\to} \; baa F aab , F \; {\to} \; baa c aab , \\
F \; {\to} \; baaa F baa , F \; {\to} \; baaa c baa ,
\end{align*}$$
и язык L2,
порождаемый грамматикой$$\begin{align*}
J \; {\to} \; ba J aa , J \; {\to} \; ba c aa , \\
J \; {\to} \; baa J bb , J \; {\to} \; baa c bb , \\
J \; {\to} \; baaa J a , J \; {\to} \; baaa c a .
\end{align*}$$
Верно ли, что $$L_1 \cap L_2 = \varnothing $$?
Теорема 16.2.1. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, является ли грамматика G однозначной.
Доказательство.
Рассмотрим язык $$\pcpl{\vec x} \cup \pcpl{\vec y} $$.
Следуя доказательству теоремы 9.4.3,
построим грамматику G
для этого языка, исходя из грамматик $$G(\vec x) $$ и $$G(\vec y) $$.
Грамматика G является неоднозначной тогда и только тогда, когда
постовская система соответствия $$( \vec x , \vec y ) $$
имеет решение.
Упражнение 16.2.2. Однозначна ли контекстно-свободная грамматика$$\begin{align*} S \; {\to} \; Q , R \; {\to} \; ba R bba , \\ S \; {\to} \; R , R \; {\to} \; baa R a , \\ Q \; {\to} \; ba Q b , R \; {\to} \; ba c bba , \\ Q \; {\to} \; baa Q abbaa , R \; {\to} \; baa c a ? \\ Q \; {\to} \; ba c b , \\ Q \; {\to} \; baa c abbaa , \end{align*}$$
Лемма 16.3.1. Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$. Язык $$\Sigma_3 ^* \sminus \pcpl{\vec x} $$ является контекстно-свободным при любом $$\vec x $$.
Пример 16.3.2.
Пусть $$\vec x = ( b , abbaa ) $$.
Тогда язык $$\Sigma_3 ^* \sminus \pcpl{\vec x} $$
над алфавитом $$\Sigma_3 = \{ a , b ,c \} $$
порождается контекстно-свободной грамматикой$$\begin{align*}
S \; {\to} \; \varepsilon , R \; {\to} \; \varepsilon , T_1 \; {\to} \; U_b , \\
S \; {\to} \; A W , R \; {\to} \; B W , T_2 \; {\to} \; U_a bbaa , \\
S \; {\to} \; b R , R \; {\to} \; aaa W , T_2 \; {\to} \; U_b baa , \\
A \; {\to} \; a , R \; {\to} \; a , T_2 \; {\to} \; U_b aa , \\
A \; {\to} \; c , R \; {\to} \; aa , T_2 \; {\to} \; U_a a , \\
B \; {\to} \; b , R \; {\to} \; ab R b , T_2 \; {\to} \; U_a , \\
B \; {\to} \; c , R \; {\to} \; aab R abbaa , U_a \; {\to} \; W B , \\
Z \; {\to} \; a , R \; {\to} \; ac Z W b , U_a \; {\to} \; \varepsilon , \\
Z \; {\to} \; B , R \; {\to} \; aac Z W abbaa , U_b \; {\to} \; W A , \\
W \; {\to} \; Z W , R \; {\to} \; a B T_1 , U_b \; {\to} \; \varepsilon . \\
W \; {\to} \; \varepsilon , R \; {\to} \; aa B T_2 ,
\end{align*}$$
Заметим, что $$\{ w \in \Sigma_3 ^* \mid T_i \overstar{\Rightarrow} w \} = \Sigma_3 ^* \sminus ( \Sigma_3 ^* \cdot \{ x_i \} ) $$
для каждого i.
Язык $$\Sigma_3 ^* \sminus \pcpl{\vec x} $$
является даже линейным
(чтобы получить линейную грамматику, достаточно "раскрыть"
вспомогательные символы A, B и Z ).
Замечание 16.3.3.
Лемму 16.3.1
можно доказать, явно построив
Определение 16.3.4.
Пусть $$\Sigma_3 = \{ a , b , c \} $$, $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$,
где $$x_i \in \{ a , b \}^* $$
и $$y_i \in \{ a , b \}^* $$
для всех i.
Обозначим через $$\pcpm{\vec x , \vec y} $$
язык $$\Sigma_3 ^* \sminus (\pcpl{\vec x} \cap \pcpl{\vec y}) $$.
Лемма 16.3.5. Язык $$\pcpm{\vec x , \vec y} $$ является контекстно-свободным при любых $$\vec x $$ и $$\vec y $$.
Доказательство. $$\pcpm{\vec x , \vec y} = (\Sigma_3 ^* \sminus \pcpl{\vec x}) \cup (\Sigma_3 ^* \sminus \pcpl{\vec y}) $$.
Лемма 16.3.6. Дополнение языка $$\pcpm{\vec x , \vec y} $$ является непустым тогда и только тогда, когда постовская система соответствия $$( \vec x , \vec y ) $$ имеет решение.
Доказательство Утверждение следует из леммы 16.1.2.
Теорема 16.3.7. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, верно ли, что $$L(G) = \Sigma ^* $$.
Доказательство
Очевидно, что $$L(G) = \Sigma ^* $$
тогда и только тогда, когда
L(G)
является пустым.
Теорема 16.3.8. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, верно ли, что L(G1) = L(G2).
Доказательство Утверждение следует из предыдущей теоремы и примера 1.5.16.
Теорема 16.3.9. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, верно ли, что $$L(G_1) \subseteq L(G_2) $$.
Доказательство Очевидно, что $$\Sigma ^* \subseteq L(G) $$ тогда и только тогда, когда $$L(G) = \Sigma ^* $$.
Лемма 16.3.10. Дополнение языка $$\pcpm{\vec x , \vec y} $$ является бесконечным тогда и только тогда, когда постовская система соответствия $$( \vec x , \vec y ) $$ имеет решение.
Теорема 16.3.11. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, является ли бесконечным множество $$\Sigma ^* \sminus L(G) $$.
Упражнение 16.3.12.
Рассмотрим язык, порождаемый грамматикой$$\begin{align*}
S \; {\to} \; F , F \; {\to} \; \varepsilon , T \; {\to} \; a , \\
S \; {\to} \; T , F \; {\to} \; a J , T \; {\to} \; b T , \\
F \; {\to} \; b F , T \; {\to} \; T b , \\
J \; {\to} \; a F , T \; {\to} \; T a T . \\
J \; {\to} \; b J ,
\end{align*}$$
Содержит ли этот язык все слова из {a,b}*?
Упражнение 16.3.13.
Рассмотрим язык, порождаемый грамматикой$$\begin{align*}
S \; {\to} \; F , T \; {\to} \; a , \\
S \; {\to} \; T , T \; {\to} \; b T , \\
F \; {\to} \; aa F , T \; {\to} \; T b , \\
F \; {\to} \; b F , T \; {\to} \; T a T . \\
F \; {\to} \; \varepsilon ,
\end{align*}$$
{a,b}*?
Лемма 16.4.1. Пусть $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$, где $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$ и $$x_i y_i \neq \varepsilon $$ для всех i. Тогда язык $$\pcpm{\vec x , \vec y} $$ является автоматным
в том и только том случае,
когда постовская система соответствия $$( \vec x , \vec y ) $$ не имеет решений.
Доказательство
Пусть $$(i_1 , \ldots , i_k) $$ -
решение постовской системы соответствия $$( \vec x , \vec y ) $$,
где $$x_i y_i \neq \varepsilon $$
для всех i.
Положим$$\begin{align*}
u \bydef b a^{i_k} b a^{i_{k-1}} \ldots b a^{i_1} ,\\
v \bydef x_{i_1} \ldots x_{i_k} ,\\
L_0 \bydef \{ u \}^* \cdot \{ c \} \cdot \{ v \}^* .
\end{align*}$$
Легко проверить, что $$u \neq \varepsilon $$, $$v \neq \varepsilon $$
и
язык L0
является автоматным.
Очевидно, что$$\pcpl{\vec x} \cap \pcpl{\vec y} \cap L_0 = \{ u^m c v^m \mid m > 0 \} .$$
Как было установлено в упражнении 3.4.2,
язык $$\pcpl{\vec x} \cap \pcpl{\vec y} \cap L_0 $$
не является автоматным.
Согласно теореме 3.2.1
язык $$\pcpl{\vec x} \cap \pcpl{\vec y} $$
не является автоматным.
Следовательно, и язык $$\pcpm{\vec x , \vec y} $$
не является автоматным.
Обратно, если постовская система соответствия $$( \vec x , \vec y ) $$ не имеет решений, то $$\pcpm{\vec x , \vec y} = \{ a , b , c \}^* $$, а этот язык является автоматным.
Теорема 16.4.2. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, является ли автоматным язык L(G).
Доказательство
Докажем утверждение теоремы для случая $$| \Sigma | \geq 3 $$.
Из леммы 16.4.1 следует, что
если бы проблема распознавания автоматности
языка L(G)
для контекстно-свободных грамматик
над алфавитом $$\Sigma $$
была разрешима, то также была бы разрешима
проблема соответствий Поста для
постовских систем соответствия $$( ( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ) ) $$,
где $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$
и $$x_i y_i \neq \varepsilon $$
для всех i.
Но тогда была бы разрешима проблема соответствий Поста для всех
постовских систем соответствия над алфавитом {a,b}
(если $$x_i y_i = \varepsilon $$
для некоторого i,
то рассматриваемая
постовская система соответствия имеет решение,
а именно (i) ).
Упражнение 16.4.3. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; R T , \\ R \; {\to} \; T R , \\ R \; {\to} \; a , \\ T \; {\to} \; T R , \\ T \; {\to} \; b ? \end{align*}$$
Упражнение 16.4.4. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} R \; {\to} \; T R , \\ R \; {\to} \; a , \\ T \; {\to} \; R , \\ T \; {\to} \; b R ? \end{align*}$$
Упражнение 16.4.5. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} R \; {\to} \; T R , \\ R \; {\to} \; a , \\ T \; {\to} \; R T , \\ T \; {\to} \; b ? \end{align*}$$
Упражнение 16.4.6. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; R T , \\ R \; {\to} \; T R , \\ R \; {\to} \; a , \\ T \; {\to} \; R T , \\ T \; {\to} \; b ? \end{align*}$$
Определение 16.5.1.
Пусть $$\Sigma_3 = \{ a , b , c \} $$, $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$,
где $$x_i \in \{ a , b \}^* $$
и $$y_i \in \{ a , b \}^* $$
для всех i.
Обозначим через $$\pcpk{\vec x , \vec y} $$
язык $$\pcpl{\vec x} \cdot \{c\} \cdot \pcpl{\vec y} \reverse $$.
Лемма 16.5.2. Язык $$\pcpk{\vec x , \vec y} $$ является контекстно-свободным при любых $$\vec x $$ и $$\vec y $$.
Доказательство Утверждение следует из теорем 9.4.4 и 9.4.2.
Лемма 16.5.3. Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$. Пусть $$\vec x = ( x_1 , \ldots , x_n ) $$ и $$\vec y = ( y_1 , \ldots , y_n ) $$, где $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$ и $$x_i y_i \neq \varepsilon $$ для всех i. Тогда язык $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$ является контекстно-свободным
в том и только том случае,
когда
постовская система соответствия $$( \vec x , \vec y ) $$ не имеет решений.
Доказательство.
Пусть $$(i_1 , \ldots , i_k) $$ -
решение постовской системы соответствия $$( \vec x , \vec y ) $$,
где $$x_i y_i \neq \varepsilon $$
для всех i.
Положим$$\begin{align*}
u \bydef b a^{i_k} b a^{i_{k-1}} \ldots b a^{i_1} ,\\
v \bydef x_{i_1} \ldots x_{i_k} ,\\
L_0 \bydef \{ u \}^* \cdot \{ c \} \cdot \{ v \}^* \cdot \{ c \} \cdot
\{ v \reverse \}^* \cdot \{ c \} \cdot \{ u \reverse \}^* .
\end{align*}$$
Легко проверить, что $$u \neq \varepsilon $$, $$v \neq \varepsilon $$
и
язык L0
является автоматным.
Очевидно,
что$$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \}
\cap L_0 =
\{ u^m c v^m c ( v \reverse )^m c ( u \reverse)^m \mid m > 0 \} .$$
Можно доказать
(например, используя лемму 9.1.1),
что язык $$\{ u^m c v^m c ( v \reverse )^m c ( u \reverse)^m \mid m > 0 \} $$
не является контекстно-свободным.
Согласно теореме 9.6.1
язык $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$
также не~является контекстно-свободным.
Обратно, если постовская система соответствия $$( \vec x , \vec y ) $$ не имеет решений, то $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} = \varnothing $$.
Теорема 16.5.4. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, является ли контекстно-свободным язык $$L(G_1) \cap L(G_2) $$.
Доказательство.
Достаточно построить по постовской системе соответствия $$( \vec x , \vec y ) $$,
где $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$
и
для всех i
выполняется $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$
и $$x_i y_i \neq \varepsilon $$,
G1,
порождающую язык $$\pcpk{\vec x , \vec y} $$,
и
G2,
порождающую язык $$\{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$.
С учетом
леммы 16.5.3
неразрешимость рассматриваемой задачи сводится к неразрешимости
проблемы соответствий Поста рассуждением,
аналогичным приведенному в доказательстве теоремы 16.4.2.
Лемма 16.5.5. Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$. Язык $$\Sigma_3 ^* \sminus (\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \}) $$ является контекстно-свободным при любых $$\vec x $$ и $$\vec y $$.
Доказательство.
Положим $$L_0 = \{ w \in \Sigma_3 ^* \mid | w |_c = 1 \} $$.
Язык $$\Sigma_3 ^* \sminus (\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \}) $$
можно представить в виде объединения пяти
Теорема 16.5.6. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, является ли контекстно-свободным язык $$\Sigma ^* \sminus L(G) $$.
Доказательство.
Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$.
Достаточно построить по постовской системе соответствия $$( \vec x , \vec y ) $$,
где $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$
и
для всех i
выполняется $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$
и $$x_i y_i \neq \varepsilon $$,
G,
порождающую язык $$\Sigma_3 ^* \sminus (\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \}) $$.
С учетом леммы 16.5.5
неразрешимость рассматриваемой задачи сводится к~неразрешимости
проблемы соответствий Поста рассуждением,
аналогичным приведенному в доказательстве теоремы 16.4.2.
Лемма 16.5.7. Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$. Язык $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$ является контекстным при любых $$\vec x $$ и $$\vec y $$.
Теорема 16.5.8. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстной грамматике G над алфавитом $$\Sigma $$ узнать, является ли контекстно-свободным язык L(G).
Доказательство.
Достаточно построить по постовской системе соответствия $$( \vec x , \vec y ) $$,
где $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$
и
для всех i
выполняется $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$
и $$x_i y_i \neq \varepsilon $$,
контекстную грамматику G,
порождающую язык $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$.
Упражнение 16.5.9.
Является ли L
порождается грамматикой$$\begin{align*}
S \; {\to} \; \varepsilon , \\
S \; {\to} \; aSbS ?
\end{align*}$$
В этой лекции рассматриваются оказавшиеся неразрешимыми алгоритмические проблемы, связанные с контекстно-свободными языками. Всюду предполагается, что в индивидуальных задачах каждый язык представлен контекстно-свободной грамматикой (но можно, конечно, использовать и автоматы с магазинной памятью).
В разделе 16.1
доказывается неразрешимость
проблемы пустоты пересечения
В разделе 16.2
доказывается неразрешимость
проблемы однозначности
В разделе 16.3
доказывается неразрешимость
проблемы равенства
В разделе 16.4
доказывается неразрешимость
проблемы
автоматности
В разделе 16.5
доказывается неразрешимость
проблем
контекстной свободности дополнения
Определение 16.1.1.
Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$.
Пусть $$\vec x = ( x_1 , \ldots , x_n ) $$,
где $$x_i \in \{ a , b \}^* $$
для всех i.
Обозначим через $$G ( \vec x ) $$
линейную грамматику $$\lalg \{ S \} , \Sigma_3 , P , S \ralg $$,
где$$P = \{ S \tto b a^i S x_i \mid 1 \leq i \leq n \} \cup
\{ S \tto b a^i c x_i \mid 1 \leq i \leq n \} .$$
Обозначим через $$\pcpl{\vec x} $$
язык, порождаемый грамматикой $$G ( \vec x ) $$.
Лемма 16.1.2. Язык $$\pcpl{\vec x} \cap \pcpl{\vec y} $$ является непустым тогда и только тогда, когда постовская система соответствия $$( \vec x , \vec y ) $$ имеет решение.
Пример 16.1.3.
Рассмотрим постовскую систему соответствия$$\domino{ b }{ bba } ,
\domino{ abbaa }{ a }$$
(то есть n = 2, $$\vec x = ( b , abbaa ) $$
и $$\vec y = ( bba , a ) $$ ).
Решениями этой системы являются последовательности (1, 1, 2), (1, 1, 2, 1, 1, 2)
и т. д.
Легко убедиться, что$$\pcpl{\vec x} \cap \pcpl{\vec y} =
\{ (baababa)^n c (bbabbaa)^n \mid n \geq 1 \} .$$
Теорема 16.1.4. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, верно ли, что $$L(G_1) \cap L(G_2) = \varnothing $$.
Доказательство. Сначала докажем утверждение теоремы для случая $$| \Sigma | \geq 3 $$. Из леммы 16.1.2 следует, что если бы проблема распознавания свойства $$L(G_1) \cap L(G_2) = \varnothing $$ для контекстно-свободных грамматик над алфавитом $$\Sigma $$ была разрешима, то проблема соответствий Поста тоже была бы разрешима. Поэтому из неразрешимости проблемы соответствий Поста следует неразрешимость проблемы распознавания свойства $$L(G_1) \cap L(G_2) = \varnothing $$ для контекстно-свободных грамматик над алфавитом $$\Sigma $$.
Чтобы доказать утверждение теоремы для случая $$| \Sigma | = 2 $$
(например, $$\Sigma = \{ d , e \} $$ ),
достаточно заменить в определении $$G (\vec x) $$
символ a на ede,
символ b на edde
и символ c на eddde.
Лемма 16.1.5. Язык $$\pcpl{\vec x} \cap \pcpl{\vec y} $$ является бесконечным тогда и только тогда, когда постовская система соответствия $$( \vec x , \vec y ) $$ имеет решение.
Доказательство. Если постовская система соответствия имеет хотя бы одно решение, то она имеет бесконечно много решений.
Теорема 16.1.6. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, является ли бесконечным язык $$L(G_1) \cap L(G_2) $$.
Упражнение 16.1.7.
Пусть $$\Sigma = \{ a, b, c, d_1, d_2, d_3 \} $$.
Рассмотрим язык L1,
порождаемый грамматикой$$\begin{align*}
F \; {\to} \; d_1 F a , \\
F \; {\to} \; d_2 F aab , \\
F \; {\to} \; d_3 F baa , \\
F \; {\to} \; c ,
\end{align*}$$
и язык L2,
порождаемый грамматикой$$\begin{align*}
J \; {\to} \; d_1 J aa , \\
J \; {\to} \; d_2 J bb , \\
J \; {\to} \; d_3 J a , \\
J \; {\to} \; c .
\end{align*}$$
Верно ли, что $$L_1 \cap L_2 = \{ c \} $$?
Упражнение 16.1.8.
Пусть $$\Sigma = \{ a, b, c, d_1, d_2, d_3 \} $$.
Рассмотрим язык L1,
порождаемый грамматикой$$\begin{align*}
F \; {\to} \; d_1 F b , F \; {\to} \; d_1 c b , \\
F \; {\to} \; d_2 F a , F \; {\to} \; d_2 c a , \\
F \; {\to} \; d_3 F aba , F \; {\to} \; d_3 c aba ,
\end{align*}$$
и язык $$L_2 $$,
порождаемый грамматикой$$\begin{align*}
J \; {\to} \; d_1 J , J \; {\to} \; d_1 c , \\
J \; {\to} \; d_2 J aa , J \; {\to} \; d_2 c aa , \\
J \; {\to} \; d_3 J b , J \; {\to} \; d_3 c b .
\end{align*}$$
Верно ли, что $$L_1 \cap L_2 = \varnothing $$?
Упражнение 16.1.9.
Пусть $$\Sigma = \{ a, b, c \} $$.
Рассмотрим язык L1,
порождаемый грамматикой$$\begin{align*}
F \; {\to} \; ba F a , F \; {\to} \; ba c a , \\
F \; {\to} \; baa F aab , F \; {\to} \; baa c aab , \\
F \; {\to} \; baaa F baa , F \; {\to} \; baaa c baa ,
\end{align*}$$
и язык L2,
порождаемый грамматикой$$\begin{align*}
J \; {\to} \; ba J aa , J \; {\to} \; ba c aa , \\
J \; {\to} \; baa J bb , J \; {\to} \; baa c bb , \\
J \; {\to} \; baaa J a , J \; {\to} \; baaa c a .
\end{align*}$$
Верно ли, что $$L_1 \cap L_2 = \varnothing $$?
Теорема 16.2.1. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, является ли грамматика G однозначной.
Доказательство.
Рассмотрим язык $$\pcpl{\vec x} \cup \pcpl{\vec y} $$.
Следуя доказательству теоремы 9.4.3,
построим грамматику G
для этого языка, исходя из грамматик $$G(\vec x) $$ и $$G(\vec y) $$.
Грамматика G является неоднозначной тогда и только тогда, когда
постовская система соответствия $$( \vec x , \vec y ) $$
имеет решение.
Упражнение 16.2.2. Однозначна ли контекстно-свободная грамматика$$\begin{align*} S \; {\to} \; Q , R \; {\to} \; ba R bba , \\ S \; {\to} \; R , R \; {\to} \; baa R a , \\ Q \; {\to} \; ba Q b , R \; {\to} \; ba c bba , \\ Q \; {\to} \; baa Q abbaa , R \; {\to} \; baa c a ? \\ Q \; {\to} \; ba c b , \\ Q \; {\to} \; baa c abbaa , \end{align*}$$
Лемма 16.3.1. Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$. Язык $$\Sigma_3 ^* \sminus \pcpl{\vec x} $$ является контекстно-свободным при любом $$\vec x $$.
Пример 16.3.2.
Пусть $$\vec x = ( b , abbaa ) $$.
Тогда язык $$\Sigma_3 ^* \sminus \pcpl{\vec x} $$
над алфавитом $$\Sigma_3 = \{ a , b ,c \} $$
порождается контекстно-свободной грамматикой$$\begin{align*}
S \; {\to} \; \varepsilon , R \; {\to} \; \varepsilon , T_1 \; {\to} \; U_b , \\
S \; {\to} \; A W , R \; {\to} \; B W , T_2 \; {\to} \; U_a bbaa , \\
S \; {\to} \; b R , R \; {\to} \; aaa W , T_2 \; {\to} \; U_b baa , \\
A \; {\to} \; a , R \; {\to} \; a , T_2 \; {\to} \; U_b aa , \\
A \; {\to} \; c , R \; {\to} \; aa , T_2 \; {\to} \; U_a a , \\
B \; {\to} \; b , R \; {\to} \; ab R b , T_2 \; {\to} \; U_a , \\
B \; {\to} \; c , R \; {\to} \; aab R abbaa , U_a \; {\to} \; W B , \\
Z \; {\to} \; a , R \; {\to} \; ac Z W b , U_a \; {\to} \; \varepsilon , \\
Z \; {\to} \; B , R \; {\to} \; aac Z W abbaa , U_b \; {\to} \; W A , \\
W \; {\to} \; Z W , R \; {\to} \; a B T_1 , U_b \; {\to} \; \varepsilon . \\
W \; {\to} \; \varepsilon , R \; {\to} \; aa B T_2 ,
\end{align*}$$
Заметим, что $$\{ w \in \Sigma_3 ^* \mid T_i \overstar{\Rightarrow} w \} = \Sigma_3 ^* \sminus ( \Sigma_3 ^* \cdot \{ x_i \} ) $$
для каждого i.
Язык $$\Sigma_3 ^* \sminus \pcpl{\vec x} $$
является даже линейным
(чтобы получить линейную грамматику, достаточно "раскрыть"
вспомогательные символы A, B и Z ).
Замечание 16.3.3.
Лемму 16.3.1
можно доказать, явно построив
Определение 16.3.4.
Пусть $$\Sigma_3 = \{ a , b , c \} $$, $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$,
где $$x_i \in \{ a , b \}^* $$
и $$y_i \in \{ a , b \}^* $$
для всех i.
Обозначим через $$\pcpm{\vec x , \vec y} $$
язык $$\Sigma_3 ^* \sminus (\pcpl{\vec x} \cap \pcpl{\vec y}) $$.
Лемма 16.3.5. Язык $$\pcpm{\vec x , \vec y} $$ является контекстно-свободным при любых $$\vec x $$ и $$\vec y $$.
Доказательство. $$\pcpm{\vec x , \vec y} = (\Sigma_3 ^* \sminus \pcpl{\vec x}) \cup (\Sigma_3 ^* \sminus \pcpl{\vec y}) $$.
Лемма 16.3.6. Дополнение языка $$\pcpm{\vec x , \vec y} $$ является непустым тогда и только тогда, когда постовская система соответствия $$( \vec x , \vec y ) $$ имеет решение.
Доказательство Утверждение следует из леммы 16.1.2.
Теорема 16.3.7. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, верно ли, что $$L(G) = \Sigma ^* $$.
Доказательство
Очевидно, что $$L(G) = \Sigma ^* $$
тогда и только тогда, когда
L(G)
является пустым.
Теорема 16.3.8. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, верно ли, что L(G1) = L(G2).
Доказательство Утверждение следует из предыдущей теоремы и примера 1.5.16.
Теорема 16.3.9. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, верно ли, что $$L(G_1) \subseteq L(G_2) $$.
Доказательство Очевидно, что $$\Sigma ^* \subseteq L(G) $$ тогда и только тогда, когда $$L(G) = \Sigma ^* $$.
Лемма 16.3.10. Дополнение языка $$\pcpm{\vec x , \vec y} $$ является бесконечным тогда и только тогда, когда постовская система соответствия $$( \vec x , \vec y ) $$ имеет решение.
Теорема 16.3.11. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, является ли бесконечным множество $$\Sigma ^* \sminus L(G) $$.
Упражнение 16.3.12.
Рассмотрим язык, порождаемый грамматикой$$\begin{align*}
S \; {\to} \; F , F \; {\to} \; \varepsilon , T \; {\to} \; a , \\
S \; {\to} \; T , F \; {\to} \; a J , T \; {\to} \; b T , \\
F \; {\to} \; b F , T \; {\to} \; T b , \\
J \; {\to} \; a F , T \; {\to} \; T a T . \\
J \; {\to} \; b J ,
\end{align*}$$
Содержит ли этот язык все слова из {a,b}*?
Упражнение 16.3.13.
Рассмотрим язык, порождаемый грамматикой$$\begin{align*}
S \; {\to} \; F , T \; {\to} \; a , \\
S \; {\to} \; T , T \; {\to} \; b T , \\
F \; {\to} \; aa F , T \; {\to} \; T b , \\
F \; {\to} \; b F , T \; {\to} \; T a T . \\
F \; {\to} \; \varepsilon ,
\end{align*}$$
{a,b}*?
Лемма 16.4.1. Пусть $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$, где $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$ и $$x_i y_i \neq \varepsilon $$ для всех i. Тогда язык $$\pcpm{\vec x , \vec y} $$ является автоматным
в том и только том случае,
когда постовская система соответствия $$( \vec x , \vec y ) $$ не имеет решений.
Доказательство
Пусть $$(i_1 , \ldots , i_k) $$ -
решение постовской системы соответствия $$( \vec x , \vec y ) $$,
где $$x_i y_i \neq \varepsilon $$
для всех i.
Положим$$\begin{align*}
u \bydef b a^{i_k} b a^{i_{k-1}} \ldots b a^{i_1} ,\\
v \bydef x_{i_1} \ldots x_{i_k} ,\\
L_0 \bydef \{ u \}^* \cdot \{ c \} \cdot \{ v \}^* .
\end{align*}$$
Легко проверить, что $$u \neq \varepsilon $$, $$v \neq \varepsilon $$
и
язык L0
является автоматным.
Очевидно, что$$\pcpl{\vec x} \cap \pcpl{\vec y} \cap L_0 = \{ u^m c v^m \mid m > 0 \} .$$
Как было установлено в упражнении 3.4.2,
язык $$\pcpl{\vec x} \cap \pcpl{\vec y} \cap L_0 $$
не является автоматным.
Согласно теореме 3.2.1
язык $$\pcpl{\vec x} \cap \pcpl{\vec y} $$
не является автоматным.
Следовательно, и язык $$\pcpm{\vec x , \vec y} $$
не является автоматным.
Обратно, если постовская система соответствия $$( \vec x , \vec y ) $$ не имеет решений, то $$\pcpm{\vec x , \vec y} = \{ a , b , c \}^* $$, а этот язык является автоматным.
Теорема 16.4.2. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, является ли автоматным язык L(G).
Доказательство
Докажем утверждение теоремы для случая $$| \Sigma | \geq 3 $$.
Из леммы 16.4.1 следует, что
если бы проблема распознавания автоматности
языка L(G)
для контекстно-свободных грамматик
над алфавитом $$\Sigma $$
была разрешима, то также была бы разрешима
проблема соответствий Поста для
постовских систем соответствия $$( ( x_1 , \ldots , x_n ) , ( y_1 , \ldots , y_n ) ) $$,
где $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$
и $$x_i y_i \neq \varepsilon $$
для всех i.
Но тогда была бы разрешима проблема соответствий Поста для всех
постовских систем соответствия над алфавитом {a,b}
(если $$x_i y_i = \varepsilon $$
для некоторого i,
то рассматриваемая
постовская система соответствия имеет решение,
а именно (i) ).
Упражнение 16.4.3. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; R T , \\ R \; {\to} \; T R , \\ R \; {\to} \; a , \\ T \; {\to} \; T R , \\ T \; {\to} \; b ? \end{align*}$$
Упражнение 16.4.4. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} R \; {\to} \; T R , \\ R \; {\to} \; a , \\ T \; {\to} \; R , \\ T \; {\to} \; b R ? \end{align*}$$
Упражнение 16.4.5. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} R \; {\to} \; T R , \\ R \; {\to} \; a , \\ T \; {\to} \; R T , \\ T \; {\to} \; b ? \end{align*}$$
Упражнение 16.4.6. Является ли автоматным язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; R T , \\ R \; {\to} \; T R , \\ R \; {\to} \; a , \\ T \; {\to} \; R T , \\ T \; {\to} \; b ? \end{align*}$$
Определение 16.5.1.
Пусть $$\Sigma_3 = \{ a , b , c \} $$, $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$,
где $$x_i \in \{ a , b \}^* $$
и $$y_i \in \{ a , b \}^* $$
для всех i.
Обозначим через $$\pcpk{\vec x , \vec y} $$
язык $$\pcpl{\vec x} \cdot \{c\} \cdot \pcpl{\vec y} \reverse $$.
Лемма 16.5.2. Язык $$\pcpk{\vec x , \vec y} $$ является контекстно-свободным при любых $$\vec x $$ и $$\vec y $$.
Доказательство Утверждение следует из теорем 9.4.4 и 9.4.2.
Лемма 16.5.3. Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$. Пусть $$\vec x = ( x_1 , \ldots , x_n ) $$ и $$\vec y = ( y_1 , \ldots , y_n ) $$, где $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$ и $$x_i y_i \neq \varepsilon $$ для всех i. Тогда язык $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$ является контекстно-свободным
в том и только том случае,
когда
постовская система соответствия $$( \vec x , \vec y ) $$ не имеет решений.
Доказательство.
Пусть $$(i_1 , \ldots , i_k) $$ -
решение постовской системы соответствия $$( \vec x , \vec y ) $$,
где $$x_i y_i \neq \varepsilon $$
для всех i.
Положим$$\begin{align*}
u \bydef b a^{i_k} b a^{i_{k-1}} \ldots b a^{i_1} ,\\
v \bydef x_{i_1} \ldots x_{i_k} ,\\
L_0 \bydef \{ u \}^* \cdot \{ c \} \cdot \{ v \}^* \cdot \{ c \} \cdot
\{ v \reverse \}^* \cdot \{ c \} \cdot \{ u \reverse \}^* .
\end{align*}$$
Легко проверить, что $$u \neq \varepsilon $$, $$v \neq \varepsilon $$
и
язык L0
является автоматным.
Очевидно,
что$$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \}
\cap L_0 =
\{ u^m c v^m c ( v \reverse )^m c ( u \reverse)^m \mid m > 0 \} .$$
Можно доказать
(например, используя лемму 9.1.1),
что язык $$\{ u^m c v^m c ( v \reverse )^m c ( u \reverse)^m \mid m > 0 \} $$
не является контекстно-свободным.
Согласно теореме 9.6.1
язык $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$
также не~является контекстно-свободным.
Обратно, если постовская система соответствия $$( \vec x , \vec y ) $$ не имеет решений, то $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} = \varnothing $$.
Теорема 16.5.4. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольным
контекстно-свободным грамматикам G1 и G2 над алфавитом $$\Sigma $$ узнать, является ли контекстно-свободным язык $$L(G_1) \cap L(G_2) $$.
Доказательство.
Достаточно построить по постовской системе соответствия $$( \vec x , \vec y ) $$,
где $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$
и
для всех i
выполняется $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$
и $$x_i y_i \neq \varepsilon $$,
G1,
порождающую язык $$\pcpk{\vec x , \vec y} $$,
и
G2,
порождающую язык $$\{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$.
С учетом
леммы 16.5.3
неразрешимость рассматриваемой задачи сводится к неразрешимости
проблемы соответствий Поста рассуждением,
аналогичным приведенному в доказательстве теоремы 16.4.2.
Лемма 16.5.5. Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$. Язык $$\Sigma_3 ^* \sminus (\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \}) $$ является контекстно-свободным при любых $$\vec x $$ и $$\vec y $$.
Доказательство.
Положим $$L_0 = \{ w \in \Sigma_3 ^* \mid | w |_c = 1 \} $$.
Язык $$\Sigma_3 ^* \sminus (\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \}) $$
можно представить в виде объединения пяти
Теорема 16.5.6. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстно-свободной грамматике G над алфавитом $$\Sigma $$ узнать, является ли контекстно-свободным язык $$\Sigma ^* \sminus L(G) $$.
Доказательство.
Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$.
Достаточно построить по постовской системе соответствия $$( \vec x , \vec y ) $$,
где $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$
и
для всех i
выполняется $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$
и $$x_i y_i \neq \varepsilon $$,
G,
порождающую язык $$\Sigma_3 ^* \sminus (\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \}) $$.
С учетом леммы 16.5.5
неразрешимость рассматриваемой задачи сводится к~неразрешимости
проблемы соответствий Поста рассуждением,
аналогичным приведенному в доказательстве теоремы 16.4.2.
Лемма 16.5.7. Рассмотрим алфавит $$\Sigma_3 = \{ a , b , c \} $$. Язык $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$ является контекстным при любых $$\vec x $$ и $$\vec y $$.
Теорема 16.5.8. Пусть $$| \Sigma | \geq 2 $$. Тогда не существует алгоритма, позволяющего по произвольной
контекстной грамматике G над алфавитом $$\Sigma $$ узнать, является ли контекстно-свободным язык L(G).
Доказательство.
Достаточно построить по постовской системе соответствия $$( \vec x , \vec y ) $$,
где $$\vec x = ( x_1 , \ldots , x_n ) $$, $$\vec y = ( y_1 , \ldots , y_n ) $$
и
для всех i
выполняется $$x_i \in \{ a , b \}^* $$, $$y_i \in \{ a , b \}^* $$
и $$x_i y_i \neq \varepsilon $$,
контекстную грамматику G,
порождающую язык $$\pcpk{\vec x , \vec y} \cap \{ z c z \reverse \mid z \in \Sigma_3 ^* \} $$.
Упражнение 16.5.9.
Является ли L
порождается грамматикой$$\begin{align*}
S \; {\to} \; \varepsilon , \\
S \; {\to} \; aSbS ?
\end{align*}$$
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.