В этой лекции рассматриваются наиболее известные разрешимые проблемы,
связанные с грамматиками, автоматами и регулярными выражениями.
Поскольку все приведенные выше доказательства эквивалентности
разных способов конечного задания формального языка
были конструктивными,
не важно, какой из эквивалентных способов задания языка
(например, посредством
Первые два раздела этой лекции посвящены контекстным языкам. В разделах 15.3-15.6 сформулированы теоремы о разрешимости для некоторых алгоритмических проблем. Доказательства этих теорем опираются на конструктивность рассуждений, проведенных в лекциях 3 и 8. В разделе 15.7* приводится новый неожиданный результат, доказанный в 1997 году.
Проблема эквивалентности конечных автоматов
(или, что то же самое, регулярных выражений)
разрешима, но, к сожалению, она сложна,
то есть нахождение ответа индивидуальной задачи
требует (в некотором смысле) много времени.
В разделе 15.9*
указывается, что даже для регулярных выражений без итерации
(которые, очевидно, соответствуют конечным автоматам без циклов)
проблема неэквивалентности NP -полна
(необходимые определения из теории сложности вычислений
приведены в разделе 15.8*).
Определение 15.1.1. Порождающая грамматика $$\lalg N , \Sigma , P , S \ralg $$ называется неукорачивающей (noncontracting), если для каждого правила $$( \alpha \tto \beta ) \in P $$ выполняется неравенство $$| \alpha | \leq | \beta | $$.
Теорема 15.1.2.
Существует алгоритм, позволяющий по произвольной
неукорачивающей грамматике G
и по слову w узнать, верно ли, что $$w \in L(G) $$.
Теорема 15.1.3. Каждая контекстная грамматика является неукорачивающей. Каждая неукорачивающая грамматика эквивалентна некоторой контекстной грамматике.
Пример 15.1.4. Грамматика$$\begin{align*} S \; {\to} \; ASTA , \\ S \; {\to} \; AbA , \\ A \; {\to} \; a , \\ bT \; {\to} \; bb , \\ AT \; {\to} \; TA \end{align*}$$ эквивалентна контекстной грамматике из примера 1.5.4.
Упражнение 15.1.5. Найти неукорачивающую грамматику, порождающую язык $$\{ w \in \{a,b,c\}^+ \mid | w |_a = | w |_b = | w |_c \} $$.
Упражнение 15.1.6. Найти неукорачивающую грамматику, порождающую язык $$\{ w \in \{a,b,c\}^* \mid | w |_a < | w |_b < | w |_c \} $$.
Упражнение 15.1.7. Найти неукорачивающую грамматику, порождающую язык $$\{ c^n d c^n d c^n \mid n \geq 0 \} $$.
Упражнение 15.1.7. Найти неукорачивающую грамматику, порождающую язык $$\{ w c w \mid w \in \{a,b\}^* \} $$.
Определение 15.2.1.
Машина Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg$$
называется линейно ограниченным автоматом
(linear |xay| > |b0wb0|.
Теорема 15.2.2. Язык L, не содержащий пустого слова,
порождается некоторой неукорачивающей грамматикой
тогда и только тогда, когда
существует
линейно ограниченный автомат
( в общем случае недетерминированный ), допускающий язык L.
Замечание 15.2.3. Неизвестно, верен ли аналог теоремы 15.2.2 для детерминированных линейно ограниченных автоматов.
Теорема 15.2.4. Класс языков, порождаемых неукорачивающими грамматиками, то есть класс контекстных языков, замкнут относительно операций объединения, пересечения и дополнения.
Замкнутость относительно
Упражнение 15.2.5. Является ли контекстным язык$$\{ w \in \{a,b,c,d\}^* \mid | w |_a \neq | w |_b ,\ | w |_c \neq | w |_d \} ?$$
Упражнение 15.2.6. Является ли контекстным язык$$\{a\}^* \sminus \{ a^{n^2} \mid n \geq 0 \} ?$$
Теорема 15.3.1. Существует алгоритм, позволяющий по произвольной
контекстно-свободной грамматике G узнать, верно ли, что $$\varepsilon \in L(G) $$.
Теорема 15.3.2. Существует алгоритм, позволяющий по произвольной
контекстно-свободной грамматике G и по слову w узнать, верно ли, что $$w \in L(G) $$.
Упражнение 15.3.3.
Принадлежит ли слово aaaaabbbabb
языку, порождаемому грамматикой$$\begin{align*}
F \; {\to} \; a F bbb , \\
F \; {\to} \; a F ba , \\
F \; {\to} \; a F a , \\
F \; {\to} \; a F abb , \\
F \; {\to} \; a ?
\end{align*}$$
Упражнение 15.3.4.
Принадлежит ли слово abababa
языку, порождаемому грамматикой$$\begin{align*}
J \; {\to} \; a a , \\
J \; {\to} \; F b F , \\
F \; {\to} \; a J , \\
F \; {\to} \; J b , \\
F \; {\to} \; b F a , \\
F \; {\to} \; \varepsilon ?
\end{align*}$$
Теорема 15.4.1.
Существует алгоритм, позволяющий по произвольной
G
узнать, верно ли, что $$L(G) = \varnothing $$.
Доказательство.
Удалим из G все бесполезные символы, кроме начального символа
(как в доказательстве теоремы 8.1.3).
Если полученная грамматика содержит хотя бы одно правило, то $$L(G) \neq \varnothing $$.
Упражнение 15.4.2. Является ли непустым язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a a C M , K \; {\to} \; b T , \\ S \; {\to} \; a a a K F , K \; {\to} \; a T , \\ M \; {\to} \; a M b , T \; {\to} \; b K a , \\ M \; {\to} \; b M a , T \; {\to} \; a b ? \\ M \; {\to} \; \varepsilon , \\ C \; {\to} \; a C a , \\ C \; {\to} \; b C b , \end{align*}$$
Теорема 15.5.1. Существует алгоритм, позволяющий по произвольной
контекстно-свободной грамматике G узнать, является ли бесконечным язык L(G).
Пример 15.5.2.
Рассмотрим
G
из примера 8.1.4.
Чтобы выяснить, является ли язык L(G)
бесконечным,
удалим сначала все бесполезные символы.
Затем устраним все $$\varepsilon $$ -правила.
Так как $$W \overstar{\Rightarrow} Z $$
и $$Z \overstar{\Rightarrow} W $$,
то можно всюду заменить W
на Z.
Получится грамматика$$\begin{align*}
S \; {\to} \; V Z , Z \; {\to} \; aab , \\
T \; {\to} \; aa , Z \; {\to} \; b , \\
T \; {\to} \; bb , \\
V \; {\to} \; a T b , \\
V \; {\to} \; b T a ,
\end{align*}$$
эквивалентная исходной грамматике G.
Очевидно, что эта грамматика не содержит
"рекурсивных" L(G)
является конечным.
Упражнение 15.5.3. Является ли бесконечным язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a F , S \; {\to} \; a a C M , C \; {\to} \; a C a , \\ F \; {\to} \; J , S \; {\to} \; a a a K F , C \; {\to} \; b C b , \\ F \; {\to} \; a , M \; {\to} \; a M b , K \; {\to} \; b T , \\ J \; {\to} \; F , M \; {\to} \; b M a , K \; {\to} \; a T , \\ J \; {\to} \; b , M \; {\to} \; \varepsilon , T \; {\to} \; b K a , \\ T \; {\to} \; a b ? \end{align*}$$
Теорема 15.6.1.
Существует алгоритм, позволяющий по произвольным двум
праволинейным грамматикам G1 и G2
узнать, верно ли, что $$L(G_1) \subseteq L(G_2) $$.
Теорема 15.6.2.
Существует алгоритм, позволяющий по произвольным двум
праволинейным грамматикам G1 и G2
узнать, верно ли, что L(G1) = L(G2).
Упражнение 15.6.3. Эквивалентны ли грамматика$$\begin{align*} S \; {\to} \; aab S , \\ S \; {\to} \; aaba \end{align*}$$ и грамматика$$\begin{align*} S \; {\to} \; a T , \\ U \; {\to} \; ba T , \\ T \; {\to} \; a U , \\ T \; {\to} \; aba ? \end{align*}$$
Теорема 15.7.1. Существует алгоритм, позволяющий по произвольным двум
детерминированным МП-автоматам M1 и M2 узнать, верно ли, что L(M1) = L(M2).
Эту теорему доказал Жеро Сенизерг (Geraud Senizergues) в 1997 году. Упрощенное доказательство приводится в [Sti].
Упражнение 15.7.2. Эквивалентны ли два изображенных ниже МП-автомата над алфавитом $$\{ a , b , \eos \} $$?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{0,-1} ^{b,AA:\varepsilon} \ar "1,2" ^{\boldsymbol{\$},\varepsilon:\varepsilon} *=[o][F=]{2} } \qquad \objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{aa,\varepsilon:B} \rloop{0,-1} ^{b,B:\varepsilon} \ar "1,2" ^{\boldsymbol{\$},\varepsilon:\varepsilon} *=[o][F=]{2} }$$
Упражнение 15.7.3. Эквивалентны ли два изображенных ниже МП-автомата над алфавитом $$\{ a , b , \eos \} $$?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \ar "1,2" ^{b,\varepsilon:\varepsilon} *=[o][F-]{2} \rloop{0,1} ^{b,AA:\varepsilon} \ar "1,3" ^{\boldsymbol{\$},\varepsilon:\varepsilon} *=[o][F=]{3} } \qquad \objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{aa,\varepsilon:B} \ar "1,2" ^{b,\varepsilon:\varepsilon} *=[o][F-]{2} \rloop{0,1} ^{b,B:\varepsilon} \ar "1,3" ^{\boldsymbol{\$},\varepsilon:\varepsilon} *=[o][F=]{3} }$$
Определение 15.8.1.
Пусть
машина Тьюринга M
допускает язык L.
Говорят, что язык L распознается за полиномиальное время на машине M,
если
существует такой многочлен p,
что
любое слово $$w \in L $$
принимается машиной M
не более чем за p(|w|)
тактов.
Определение 15.8.2.
Через P
обозначается класс тех языков,
которые распознаются за полиномиальное время на некоторой
детерминированной машине Тьюринга.
Определение 15.8.3.
Через NP
обозначается класс тех формальных языков,
которые распознаются за полиномиальное время на некоторой
(в общем случае недетерминированной) машине Тьюринга.
Замечание 15.8.4.
Очевидно, что $$\mathrm{P} \subseteq \mathrm{NP} $$.
Неизвестно, совпадают ли классы P и NP.
Теорема 15.8.5. Все языки из класса NP являются разрешимыми.
Определение 15.8.6.
f
из $$\Sigma_1^* $$
в $$\Sigma_2^* $$
называется вычислимой за полиномиальное время,
если
ее вычисляет некоторая
детерминированная машина Тьюринга M
(если $$\Sigma_1 \neq \Sigma_2 $$, то данная функция f
рассматривается как частичная функция
из $$(\Sigma_1 \cup \Sigma_2)^* $$
в $$(\Sigma_1 \cup \Sigma_2)^* $$ )
и
существует такой многочлен p,
что для любого слова $$w \in \Sigma_1^* $$
машина M
вычисляет значение f(w)
не более чем за p(|w|)
тактов.
Определение 15.8.7.
Язык $$L_1 \subseteq \Sigma_1^* $$ полиномиально сводится (is f
из $$\Sigma_1^* $$
в $$\Sigma_2^* $$,
что
для любого слова $$w \in \Sigma_1^* $$
условие $$f ( w ) \in L_2 $$
равносильно
условию $$w \in L_1 $$.
Определение 15.8.8.
Формальный язык L
называется
NP- сложным (NP-hard},
если
каждый язык из класса NP
полиномиально сводится к языку L.
Определение 15.8.9.
Формальный язык называется
NP- полным (NP
и является NP -сложным.
Определение 15.8.10. Алгоритмическая проблема, относящаяся к некоторой задаче распознавания, называется NP- полной, если множество кодов индивидуальных задач с ответом "да" является NP-полным языком.
Теорема 15.8.11 (теорема Кука-Левина). Проблема выполнимости булевых формул в конъюнктивной нормальной форме N- полна.
Доказательство можно найти, например, в [Сэв, с. 325-328] или [ГэрДжо, с. 57-63].
Упражнение 15.8.12.
Существует ли такой язык $$L \subseteq \Sigma^* $$
из класса P,
что язык $$\Sigma^* \sminus L $$
не принадлежит классу P?
Упражнение 15.8.13.
Существуют ли такие языки L1 и L2
из класса P,
что язык $$L_1 \cup L_2 $$
не принадлежит классу P?
Упражнение 15.8.14.
Существуют ли такие языки L1 и L2
из класса NP,
что язык $$L_1 \cup L_2 $$
не принадлежит классу NP?
Теорема 15.9.1. Проблема неравенства регулярных выражений без итерации ( то есть регулярных выражений с нулевой звездной высотой ) NP- полна.
Доказательство.
По регулярному выражению без итерации легко построить
конечный автомат с однобуквенными переходами, не содержащий циклов.
Проблема неравенства таких конечных автоматов
принадлежит классу NP:
достаточно "угадать" слово, принадлежащее
разности языков, распознаваемых двумя данными автоматами,
и, продвигаясь по этому слову буква за буквой,
подобно доказательству теоремы 2.7.1
вычислять, в каких состояниях автоматы могут оказаться.
При этом длину слова можно ограничить максимумом числа состояний
двух автоматов.
Осталось доказать, что проблема неравенства
регулярных выражений без итерации
NP-сложна.
Для этого достаточно продемонстрировать, что
к этой проблеме полиномиально сводится проблема
выполнимости
Пусть дана
x1, x2, ..., xn
(при более формальном подходе можно считать xi обозначением слова p#i,
как это сделано в примере 7.2.8).
Здесь для каждого $$j \leq m $$
формула Cj
является xi
через $$\overline{x_i} $$
(а не через $$\lnot x_i $$,
как в примере 7.2.8).
Построим два регулярных выражения над алфавитом $$\Sigma = \{a,b\} $$.
В качестве первого
регулярного выражения
возьмем$$\underbrace{ (a+b) \cdot (a+b) \cdot \ldots \cdot (a+b) }_{n \text{ раз}} .$$
Для удобства отождествим a и b
соответственно.
Тогда оценку пропозициональных переменных x1, x2, ..., xn
можно естественным образом отождествить со словом длины n
в алфавите $$\Sigma $$.
Второе
регулярное выражение e
построим так, чтобы выполнялось равенство$$\regval{e} = \{ w \in \Sigma^* \mid
| w | = n
\rusand
C_1 \land C_2 \land \ldots \land C_m
\mathspace\text{ложна при оценке}\mathspace w \} .$$
Если m = 1,
то это сделать легко.
Возьмем в качестве e
произведение n сомножителей,
каждый из которых совпадает с~одним из следующих
четырех регулярных выражений: (a + b), a, b, 0.
При этом i -й сомножитель соответствует пропозициональной переменной xi
и выбирается следующим образом:
xi,
ни литерала $$\overline{x_i} $$,
то используем выражение (a+b) ;xi,
но не содержит
литерала $$\overline{x_i} $$,
то используем выражение a ;xi,
то используем выражение b ;xi и $$\overline{x_i} $$,
то используем выражение 0.Если m > 1,
то построим по указанному методу
для каждой из C1, C2, ..., Cm
регулярное выражение и возьмем их сумму.
Легко видеть, что
два построенных так регулярных выражения равны тогда и только тогда,
когда
Пример 15.9.2. Пусть $$\Sigma = \{ a , b \} $$. Регулярные выражения
(a+b)(a+b)(a+b)
и
ab(a+b)+(a+b)ab+b(a+b)(a+b)+(a+b)(a+b)a
равны, так как
Упражнение 15.9.3. Равны ли регулярные выражения
(a+b)(a+b)(a+b)
и
bb(a+b)+ba(a+b)+a(a+b)b+(a+b)aa ?
Упражнение 15.9.4. Равны ли регулярные выражения
(a+b)(a+b)(a+b)(a+b)
и
aab(a+b)+a(a+b)(a+b)b+(a+b)aa(a+b)+(a+b)bb(a+b)+
+(a+b)baa+bab(a+b)+b(a+b)(a+b)b ?
Упражнение 15.9.5. Эквивалентен ли конечный автомат$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" <0.6mm> ^{a} \ar "1,2" <-0.6mm> _{b} *=[o][F-]{2} \ar "1,3" <0.6mm> ^{a} \ar "1,3" <-0.6mm> _{b} *=[o][F-]{3} \ar "1,4" <0.6mm> ^{a} \ar "1,4" <-0.6mm> _{b} *=[o][F=]{4} }$$ конечному автомату, изображенному ниже?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "4,1" <0.6mm> ^{a} \ar "4,1" <-0.6mm> _{b} \ar "2,2" ^{a} \ar "1,4" _{b} *=[o][F-]{4} \ar "4,4" <0.6mm> ^{a} \ar "4,4" <-0.6mm> _{b} \ar "2,3" _{b} \\ % *=[o][F-]{2} \ar "3,2" <0.6mm> ^{a} \ar "3,2" <-0.6mm> _{b} \ar "2,3" ^{a} *=[o][F-]{6} \ar "3,3" <0.6mm> ^{a} \ar "3,3" <-0.6mm> _{b} \\ % *=[o][F-]{3} \ar "3,3" _{a} *=[o][F=]{7} \\ *=[o][F-]{1} \ar "3,2" _{a} \ar "4,4" ^{b} *=[o][F-]{5} \ar "3,3" ^{b} }$$
В этой лекции рассматриваются наиболее известные разрешимые проблемы,
связанные с грамматиками, автоматами и регулярными выражениями.
Поскольку все приведенные выше доказательства эквивалентности
разных способов конечного задания формального языка
были конструктивными,
не важно, какой из эквивалентных способов задания языка
(например, посредством
Первые два раздела этой лекции посвящены контекстным языкам. В разделах 15.3-15.6 сформулированы теоремы о разрешимости для некоторых алгоритмических проблем. Доказательства этих теорем опираются на конструктивность рассуждений, проведенных в лекциях 3 и 8. В разделе 15.7* приводится новый неожиданный результат, доказанный в 1997 году.
Проблема эквивалентности конечных автоматов
(или, что то же самое, регулярных выражений)
разрешима, но, к сожалению, она сложна,
то есть нахождение ответа индивидуальной задачи
требует (в некотором смысле) много времени.
В разделе 15.9*
указывается, что даже для регулярных выражений без итерации
(которые, очевидно, соответствуют конечным автоматам без циклов)
проблема неэквивалентности NP -полна
(необходимые определения из теории сложности вычислений
приведены в разделе 15.8*).
Определение 15.1.1. Порождающая грамматика $$\lalg N , \Sigma , P , S \ralg $$ называется неукорачивающей (noncontracting), если для каждого правила $$( \alpha \tto \beta ) \in P $$ выполняется неравенство $$| \alpha | \leq | \beta | $$.
Теорема 15.1.2.
Существует алгоритм, позволяющий по произвольной
неукорачивающей грамматике G
и по слову w узнать, верно ли, что $$w \in L(G) $$.
Теорема 15.1.3. Каждая контекстная грамматика является неукорачивающей. Каждая неукорачивающая грамматика эквивалентна некоторой контекстной грамматике.
Пример 15.1.4. Грамматика$$\begin{align*} S \; {\to} \; ASTA , \\ S \; {\to} \; AbA , \\ A \; {\to} \; a , \\ bT \; {\to} \; bb , \\ AT \; {\to} \; TA \end{align*}$$ эквивалентна контекстной грамматике из примера 1.5.4.
Упражнение 15.1.5. Найти неукорачивающую грамматику, порождающую язык $$\{ w \in \{a,b,c\}^+ \mid | w |_a = | w |_b = | w |_c \} $$.
Упражнение 15.1.6. Найти неукорачивающую грамматику, порождающую язык $$\{ w \in \{a,b,c\}^* \mid | w |_a < | w |_b < | w |_c \} $$.
Упражнение 15.1.7. Найти неукорачивающую грамматику, порождающую язык $$\{ c^n d c^n d c^n \mid n \geq 0 \} $$.
Упражнение 15.1.7. Найти неукорачивающую грамматику, порождающую язык $$\{ w c w \mid w \in \{a,b\}^* \} $$.
Определение 15.2.1.
Машина Тьюринга$$\lalg Q , \Sigma , \Gamma , b_0 , \Delta , I , F \ralg$$
называется линейно ограниченным автоматом
(linear |xay| > |b0wb0|.
Теорема 15.2.2. Язык L, не содержащий пустого слова,
порождается некоторой неукорачивающей грамматикой
тогда и только тогда, когда
существует
линейно ограниченный автомат
( в общем случае недетерминированный ), допускающий язык L.
Замечание 15.2.3. Неизвестно, верен ли аналог теоремы 15.2.2 для детерминированных линейно ограниченных автоматов.
Теорема 15.2.4. Класс языков, порождаемых неукорачивающими грамматиками, то есть класс контекстных языков, замкнут относительно операций объединения, пересечения и дополнения.
Замкнутость относительно
Упражнение 15.2.5. Является ли контекстным язык$$\{ w \in \{a,b,c,d\}^* \mid | w |_a \neq | w |_b ,\ | w |_c \neq | w |_d \} ?$$
Упражнение 15.2.6. Является ли контекстным язык$$\{a\}^* \sminus \{ a^{n^2} \mid n \geq 0 \} ?$$
Теорема 15.3.1. Существует алгоритм, позволяющий по произвольной
контекстно-свободной грамматике G узнать, верно ли, что $$\varepsilon \in L(G) $$.
Теорема 15.3.2. Существует алгоритм, позволяющий по произвольной
контекстно-свободной грамматике G и по слову w узнать, верно ли, что $$w \in L(G) $$.
Упражнение 15.3.3.
Принадлежит ли слово aaaaabbbabb
языку, порождаемому грамматикой$$\begin{align*}
F \; {\to} \; a F bbb , \\
F \; {\to} \; a F ba , \\
F \; {\to} \; a F a , \\
F \; {\to} \; a F abb , \\
F \; {\to} \; a ?
\end{align*}$$
Упражнение 15.3.4.
Принадлежит ли слово abababa
языку, порождаемому грамматикой$$\begin{align*}
J \; {\to} \; a a , \\
J \; {\to} \; F b F , \\
F \; {\to} \; a J , \\
F \; {\to} \; J b , \\
F \; {\to} \; b F a , \\
F \; {\to} \; \varepsilon ?
\end{align*}$$
Теорема 15.4.1.
Существует алгоритм, позволяющий по произвольной
G
узнать, верно ли, что $$L(G) = \varnothing $$.
Доказательство.
Удалим из G все бесполезные символы, кроме начального символа
(как в доказательстве теоремы 8.1.3).
Если полученная грамматика содержит хотя бы одно правило, то $$L(G) \neq \varnothing $$.
Упражнение 15.4.2. Является ли непустым язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a a C M , K \; {\to} \; b T , \\ S \; {\to} \; a a a K F , K \; {\to} \; a T , \\ M \; {\to} \; a M b , T \; {\to} \; b K a , \\ M \; {\to} \; b M a , T \; {\to} \; a b ? \\ M \; {\to} \; \varepsilon , \\ C \; {\to} \; a C a , \\ C \; {\to} \; b C b , \end{align*}$$
Теорема 15.5.1. Существует алгоритм, позволяющий по произвольной
контекстно-свободной грамматике G узнать, является ли бесконечным язык L(G).
Пример 15.5.2.
Рассмотрим
G
из примера 8.1.4.
Чтобы выяснить, является ли язык L(G)
бесконечным,
удалим сначала все бесполезные символы.
Затем устраним все $$\varepsilon $$ -правила.
Так как $$W \overstar{\Rightarrow} Z $$
и $$Z \overstar{\Rightarrow} W $$,
то можно всюду заменить W
на Z.
Получится грамматика$$\begin{align*}
S \; {\to} \; V Z , Z \; {\to} \; aab , \\
T \; {\to} \; aa , Z \; {\to} \; b , \\
T \; {\to} \; bb , \\
V \; {\to} \; a T b , \\
V \; {\to} \; b T a ,
\end{align*}$$
эквивалентная исходной грамматике G.
Очевидно, что эта грамматика не содержит
"рекурсивных" L(G)
является конечным.
Упражнение 15.5.3. Является ли бесконечным язык, порождаемый грамматикой$$\begin{align*} S \; {\to} \; a F , S \; {\to} \; a a C M , C \; {\to} \; a C a , \\ F \; {\to} \; J , S \; {\to} \; a a a K F , C \; {\to} \; b C b , \\ F \; {\to} \; a , M \; {\to} \; a M b , K \; {\to} \; b T , \\ J \; {\to} \; F , M \; {\to} \; b M a , K \; {\to} \; a T , \\ J \; {\to} \; b , M \; {\to} \; \varepsilon , T \; {\to} \; b K a , \\ T \; {\to} \; a b ? \end{align*}$$
Теорема 15.6.1.
Существует алгоритм, позволяющий по произвольным двум
праволинейным грамматикам G1 и G2
узнать, верно ли, что $$L(G_1) \subseteq L(G_2) $$.
Теорема 15.6.2.
Существует алгоритм, позволяющий по произвольным двум
праволинейным грамматикам G1 и G2
узнать, верно ли, что L(G1) = L(G2).
Упражнение 15.6.3. Эквивалентны ли грамматика$$\begin{align*} S \; {\to} \; aab S , \\ S \; {\to} \; aaba \end{align*}$$ и грамматика$$\begin{align*} S \; {\to} \; a T , \\ U \; {\to} \; ba T , \\ T \; {\to} \; a U , \\ T \; {\to} \; aba ? \end{align*}$$
Теорема 15.7.1. Существует алгоритм, позволяющий по произвольным двум
детерминированным МП-автоматам M1 и M2 узнать, верно ли, что L(M1) = L(M2).
Эту теорему доказал Жеро Сенизерг (Geraud Senizergues) в 1997 году. Упрощенное доказательство приводится в [Sti].
Упражнение 15.7.2. Эквивалентны ли два изображенных ниже МП-автомата над алфавитом $$\{ a , b , \eos \} $$?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \rloop{0,-1} ^{b,AA:\varepsilon} \ar "1,2" ^{\boldsymbol{\$},\varepsilon:\varepsilon} *=[o][F=]{2} } \qquad \objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{aa,\varepsilon:B} \rloop{0,-1} ^{b,B:\varepsilon} \ar "1,2" ^{\boldsymbol{\$},\varepsilon:\varepsilon} *=[o][F=]{2} }$$
Упражнение 15.7.3. Эквивалентны ли два изображенных ниже МП-автомата над алфавитом $$\{ a , b , \eos \} $$?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{a,\varepsilon:A} \ar "1,2" ^{b,\varepsilon:\varepsilon} *=[o][F-]{2} \rloop{0,1} ^{b,AA:\varepsilon} \ar "1,3" ^{\boldsymbol{\$},\varepsilon:\varepsilon} *=[o][F=]{3} } \qquad \objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \rloop{0,1} ^{aa,\varepsilon:B} \ar "1,2" ^{b,\varepsilon:\varepsilon} *=[o][F-]{2} \rloop{0,1} ^{b,B:\varepsilon} \ar "1,3" ^{\boldsymbol{\$},\varepsilon:\varepsilon} *=[o][F=]{3} }$$
Определение 15.8.1.
Пусть
машина Тьюринга M
допускает язык L.
Говорят, что язык L распознается за полиномиальное время на машине M,
если
существует такой многочлен p,
что
любое слово $$w \in L $$
принимается машиной M
не более чем за p(|w|)
тактов.
Определение 15.8.2.
Через P
обозначается класс тех языков,
которые распознаются за полиномиальное время на некоторой
детерминированной машине Тьюринга.
Определение 15.8.3.
Через NP
обозначается класс тех формальных языков,
которые распознаются за полиномиальное время на некоторой
(в общем случае недетерминированной) машине Тьюринга.
Замечание 15.8.4.
Очевидно, что $$\mathrm{P} \subseteq \mathrm{NP} $$.
Неизвестно, совпадают ли классы P и NP.
Теорема 15.8.5. Все языки из класса NP являются разрешимыми.
Определение 15.8.6.
f
из $$\Sigma_1^* $$
в $$\Sigma_2^* $$
называется вычислимой за полиномиальное время,
если
ее вычисляет некоторая
детерминированная машина Тьюринга M
(если $$\Sigma_1 \neq \Sigma_2 $$, то данная функция f
рассматривается как частичная функция
из $$(\Sigma_1 \cup \Sigma_2)^* $$
в $$(\Sigma_1 \cup \Sigma_2)^* $$ )
и
существует такой многочлен p,
что для любого слова $$w \in \Sigma_1^* $$
машина M
вычисляет значение f(w)
не более чем за p(|w|)
тактов.
Определение 15.8.7.
Язык $$L_1 \subseteq \Sigma_1^* $$ полиномиально сводится (is f
из $$\Sigma_1^* $$
в $$\Sigma_2^* $$,
что
для любого слова $$w \in \Sigma_1^* $$
условие $$f ( w ) \in L_2 $$
равносильно
условию $$w \in L_1 $$.
Определение 15.8.8.
Формальный язык L
называется
NP- сложным (NP-hard},
если
каждый язык из класса NP
полиномиально сводится к языку L.
Определение 15.8.9.
Формальный язык называется
NP- полным (NP
и является NP -сложным.
Определение 15.8.10. Алгоритмическая проблема, относящаяся к некоторой задаче распознавания, называется NP- полной, если множество кодов индивидуальных задач с ответом "да" является NP-полным языком.
Теорема 15.8.11 (теорема Кука-Левина). Проблема выполнимости булевых формул в конъюнктивной нормальной форме N- полна.
Доказательство можно найти, например, в [Сэв, с. 325-328] или [ГэрДжо, с. 57-63].
Упражнение 15.8.12.
Существует ли такой язык $$L \subseteq \Sigma^* $$
из класса P,
что язык $$\Sigma^* \sminus L $$
не принадлежит классу P?
Упражнение 15.8.13.
Существуют ли такие языки L1 и L2
из класса P,
что язык $$L_1 \cup L_2 $$
не принадлежит классу P?
Упражнение 15.8.14.
Существуют ли такие языки L1 и L2
из класса NP,
что язык $$L_1 \cup L_2 $$
не принадлежит классу NP?
Теорема 15.9.1. Проблема неравенства регулярных выражений без итерации ( то есть регулярных выражений с нулевой звездной высотой ) NP- полна.
Доказательство.
По регулярному выражению без итерации легко построить
конечный автомат с однобуквенными переходами, не содержащий циклов.
Проблема неравенства таких конечных автоматов
принадлежит классу NP:
достаточно "угадать" слово, принадлежащее
разности языков, распознаваемых двумя данными автоматами,
и, продвигаясь по этому слову буква за буквой,
подобно доказательству теоремы 2.7.1
вычислять, в каких состояниях автоматы могут оказаться.
При этом длину слова можно ограничить максимумом числа состояний
двух автоматов.
Осталось доказать, что проблема неравенства
регулярных выражений без итерации
NP-сложна.
Для этого достаточно продемонстрировать, что
к этой проблеме полиномиально сводится проблема
выполнимости
Пусть дана
x1, x2, ..., xn
(при более формальном подходе можно считать xi обозначением слова p#i,
как это сделано в примере 7.2.8).
Здесь для каждого $$j \leq m $$
формула Cj
является xi
через $$\overline{x_i} $$
(а не через $$\lnot x_i $$,
как в примере 7.2.8).
Построим два регулярных выражения над алфавитом $$\Sigma = \{a,b\} $$.
В качестве первого
регулярного выражения
возьмем$$\underbrace{ (a+b) \cdot (a+b) \cdot \ldots \cdot (a+b) }_{n \text{ раз}} .$$
Для удобства отождествим a и b
соответственно.
Тогда оценку пропозициональных переменных x1, x2, ..., xn
можно естественным образом отождествить со словом длины n
в алфавите $$\Sigma $$.
Второе
регулярное выражение e
построим так, чтобы выполнялось равенство$$\regval{e} = \{ w \in \Sigma^* \mid
| w | = n
\rusand
C_1 \land C_2 \land \ldots \land C_m
\mathspace\text{ложна при оценке}\mathspace w \} .$$
Если m = 1,
то это сделать легко.
Возьмем в качестве e
произведение n сомножителей,
каждый из которых совпадает с~одним из следующих
четырех регулярных выражений: (a + b), a, b, 0.
При этом i -й сомножитель соответствует пропозициональной переменной xi
и выбирается следующим образом:
xi,
ни литерала $$\overline{x_i} $$,
то используем выражение (a+b) ;xi,
но не содержит
литерала $$\overline{x_i} $$,
то используем выражение a ;xi,
то используем выражение b ;xi и $$\overline{x_i} $$,
то используем выражение 0.Если m > 1,
то построим по указанному методу
для каждой из C1, C2, ..., Cm
регулярное выражение и возьмем их сумму.
Легко видеть, что
два построенных так регулярных выражения равны тогда и только тогда,
когда
Пример 15.9.2. Пусть $$\Sigma = \{ a , b \} $$. Регулярные выражения
(a+b)(a+b)(a+b)
и
ab(a+b)+(a+b)ab+b(a+b)(a+b)+(a+b)(a+b)a
равны, так как
Упражнение 15.9.3. Равны ли регулярные выражения
(a+b)(a+b)(a+b)
и
bb(a+b)+ba(a+b)+a(a+b)b+(a+b)aa ?
Упражнение 15.9.4. Равны ли регулярные выражения
(a+b)(a+b)(a+b)(a+b)
и
aab(a+b)+a(a+b)(a+b)b+(a+b)aa(a+b)+(a+b)bb(a+b)+
+(a+b)baa+bab(a+b)+b(a+b)(a+b)b ?
Упражнение 15.9.5. Эквивалентен ли конечный автомат$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{1} \ar @`{+/l16mm/} [] ^{} \ar "1,2" <0.6mm> ^{a} \ar "1,2" <-0.6mm> _{b} *=[o][F-]{2} \ar "1,3" <0.6mm> ^{a} \ar "1,3" <-0.6mm> _{b} *=[o][F-]{3} \ar "1,4" <0.6mm> ^{a} \ar "1,4" <-0.6mm> _{b} *=[o][F=]{4} }$$ конечному автомату, изображенному ниже?$$\objectwidth={5mm} \objectheight={5mm} \let\objectstyle=\scriptstyle \xymatrix { *=[o][F-]{0} \ar @`{+/l16mm/} [] ^{} \ar "4,1" <0.6mm> ^{a} \ar "4,1" <-0.6mm> _{b} \ar "2,2" ^{a} \ar "1,4" _{b} *=[o][F-]{4} \ar "4,4" <0.6mm> ^{a} \ar "4,4" <-0.6mm> _{b} \ar "2,3" _{b} \\ % *=[o][F-]{2} \ar "3,2" <0.6mm> ^{a} \ar "3,2" <-0.6mm> _{b} \ar "2,3" ^{a} *=[o][F-]{6} \ar "3,3" <0.6mm> ^{a} \ar "3,3" <-0.6mm> _{b} \\ % *=[o][F-]{3} \ar "3,3" _{a} *=[o][F=]{7} \\ *=[o][F-]{1} \ar "3,2" _{a} \ar "4,4" ^{b} *=[o][F-]{5} \ar "3,3" ^{b} }$$
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.