Содержание

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

В разделе 16.1 доказывается неразрешимость проблемы пустоты пересечения контекстно-свободных языков и проблемы бесконечности пересечения контекстно-свободных языков.

В разделе 16.2 доказывается неразрешимость проблемы однозначности контекстно-свободной грамматики.

В разделе 16.3 доказывается неразрешимость проблемы равенства контекстно-свободных языков.

В разделе 16.4 доказывается неразрешимость проблемы автоматности контекстно-свободного языка.

В разделе 16.5 доказывается неразрешимость проблем контекстной свободности дополнения контекстно-свободного языка и пересечения контекстно-свободных языков.

16.1. Пересечение контекстно-свободных языков

Определение 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$ . Тогда не существует алгоритма, позволяющего по произвольным контекстно-свободным грамматикам G₁ и G₂ над алфавитом $\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$ . Тогда не существует алгоритма, позволяющего по произвольным контекстно-свободным грамматикам G₁ и G₂ над алфавитом $\Sigma$ узнать, является ли бесконечным язык $L(G_1) \cap L(G_2)$ .

Упражнение 16.1.7. Пусть $\Sigma = \{ a, b, c, d_1, d_2, d_3 \}$ . Рассмотрим язык L₁, порождаемый грамматикой

$\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*}$

и язык L₂, порождаемый грамматикой

$\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 \}$ . Рассмотрим язык L₁, порождаемый грамматикой

$\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 \}$ . Рассмотрим язык L₁, порождаемый грамматикой

$\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*}$

и язык L₂, порождаемый грамматикой

$\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.1. Пересечение контекстно-свободных языков

Вопросы и Ответы