Разрешимые и перечислимые множества

Определение 14.2.1. Говорят, что детерминированная машина Тьюринга

с выделенным состоянием q_a разрешает (decides) язык , если

1) для каждого слова найдутся такие и , что ;

2) для каждого слова найдутся такие и , что . Состояние q_a называется допускающим (принимающим, accept state), состояние q_r называется отвергающим (непринимающим, (reject state).

Пример 14.2.2. Рассмотрим детерминированную машину Тьюринга

где , , , , , , и

Эта машина Тьюринга разрешает язык .

Определение 14.2.3. Язык L над алфавитом называется разрешимым или рекурсивным (decidable, recursive), если существует детерминированная машина Тьюринга

(с выделенным состоянием q_a), которая разрешает язык L.

Определение 14.2.4. Говорят, что машина Тьюринга

допускает (принимает, accepts) слово , если для некоторых и .

Определение 14.2.5. Язык, допускаемый машиной Тьюринга M, - это язык, состоящий из всех допускаемых данной машиной Тьюринга слов.

Определение 14.2.6. Язык называется перечислимым (рекурсивно перечислимым, полуразрешимым, recursively enumerable), если существует детерминированная машина Тьюринга, допускающая этот язык.

Замечание 14.2.7. В определении 14.2.6 можно отбросить требование детерминированности машины Тьюринга.

Теорема 14.2.8. Каждый разрешимый язык является перечислимым.

Доказательство. Пусть дана машина Тьюринга

с выделенным состоянием q_a, которая разрешает язык . Тогда машина Тьюринга

допускает язык L.

Пример 14.2.9. Если в машине Тьюринга из примера 14.1.15 заменить переход на , то получится машина Тьюринга, допускающая язык . Следовательно, этот язык является перечислимым. Можно доказать, что он даже является разрешимым.

Теорема 14.2.10. Существует такая машина Тьюринга над однобуквенным алфавитом , что язык, допускаемый этой машиной Тьюринга, неразрешим.

Доказательство. Доказательство существования перечислимого неразрешимого множества можно найти, например, в [31, 9.2].

Упражнение 14.2.11. Найти детерминированную машину Тьюринга с входным алфавитом {a}, разрешающую язык .

Упражнение 14.2.12. Найти детерминированную машину Тьюринга с входным алфавитом {a}, допускающую язык

Массовые задачи

Определение 14.3.1. Массовой задачей (problem) называется бесконечная серия "однотипных" индивидуальных задач (instance), каждая из которых имеет определенный ответ. С каждой массовой задачей связана некоторая фиксированная схема кодирования (encoding scheme), которая отображает индивидуальные задачи в их коды - слова в некотором фиксированном алфавите. При этом требуется, чтобы множество кодов всех индивидуальных задач было разрешимым.

Определение 14.3.2. Задачей распознавания (decision problem) называется массовая задача, в которой ответами индивидуальных задач могут быть только "да" и "нет" (то есть существует только два возможных ответа).

Пример 14.3.3. Зафиксируем некоторый алфавит . Рассмотрим следующие однотипные индивидуальные задачи: даны два слова и , необходимо выяснить, является ли слово x подсловом слова y.

Пусть # - новый символ, не принадлежащий алфавиту . Кодом индивидуальной задачи про конкретные слова x и yбудем считать слово x#y в алфавите .

Эта массовая задача является задачей распознавания.

Определение 14.3.4. Алгоритмическая проблема - проблема, в которой требуется найти алгоритм для решения массовой задачи. Если такой алгоритм существует, то данная проблема называется алгоритмически разрешимой или просто разрешимой (decidable, solvable), в противном случае ее называют алгоритмически неразрешимой (undecidable, unsolvable).

Замечание 14.3.5. Алгоритмическая проблема, относящаяся к некоторой задаче распознавания, алгоритмически разрешима тогда и только тогда, когда разрешимо множество кодов индивидуальных задач с ответом "да".

Пример 14.3.6. Рассмотрим массовую задачу из примера 14.3.3. Соответствующая алгоритмическая проблема разрешима, так как разрешим язык .

Пример 14.3.7. Зафиксируем некоторый алфавит . Рассмотрим следующие однотипные индивидуальные задачи: дана порождающая грамматика

необходимо выяснить, является ли эта грамматика праволинейной.

Для полной строгости необходимо договориться, как кодировать грамматику G в виде слова. Например, можно использовать алфавит , где - дополнительные символы, не принадлежащие множеству . Вспомогательный символ A_i заменим на слово, состоящее из символа и кода числа i в двоичной системе счисления. В каждом правиле добавим символ на месте и после слова . Кодом грамматики G будем считать результат конкатенации кодов всех правил из множества P. Например, грамматика

(над алфавитом ) кодируется словом

Легко понять, что соответствующая алгоритмическая проблема (проблема проверки праволинейности) разрешима.

Упражнение 14.3.8. Разрешима ли алгоритмическая проблема распознавания четности длины слова над алфавитом {a,b}?

14.4*. Грамматики типа 0

Теорема 14.4.1. Класс языков, порождаемых грамматиками типа 0, совпадает с классом перечислимых языков.

Доказательство можно найти, например, в [СерГал с. 24-26].

Упражнение 14.4.2. Выводимо ли слово aab в грамматике

Упражнение 14.4.3. Выводимо ли слово aaaaaaaab в грамматике

Замечание 14.4.4. Неизвестно, порождает ли грамматика

все слова в алфавите {a,b}.

Упражнение 14.4.5. Пусть . Рассмотрим грамматику

Выводимо ли в ней слово ccdcdcddccddcdcccabba?

Упражнение 14.4.6. Является ли разрешимым язык, порождаемый грамматикой

Определение 14.4.7. Порождающая грамматика в нормальной форме - это порождающая грамматика, в которой каждое правило имеет вид , или , где , , , .

Теорема 14.4.8. Каждая порождающая грамматика эквивалентна некоторой порождающей грамматике в нормальной форме.

Упражнение 14.4.9. Существует ли такая порождающая грамматика G, что язык не порождается ни одной грамматикой типа 0?

Проблема соответствий Поста

Определение 14.5.1. Постовской системой соответствия над алфавитом называется упорядоченная пара конечных последовательностей , где и для всех i.

Замечание 14.5.2. Систему иногда изображают в виде

Определение 14.5.3. Решением (match) постовской системы соответствия ((x₁,...,x_n),(y₁,...,y_n)) называется непустая последовательность индексов , удовлетворяющая условию

где для каждого j.

Пример 14.5.4. Пусть . Рассмотрим постовскую систему соответствия

Последовательность (2,1,3,2,2) является решением этой системы, так как

Упражнение 14.5.5. Пусть . Существует ли решение у постовской системы соответствия

Определение 14.5.6. Проблемой соответствий Поста (Post correspondence problem) называется проблема нахождения алгоритма, выясняющего для каждой постовской системы соответствия, существует ли решение этой системы.

Теорема 14.5.7. Пусть . Тогда не существует алгоритма, позволяющего по произвольной постовской системе соответствия над алфавитом узнать, имеет ли она решение. (Другими словами, проблема соответствий Поста неразрешима.)

Доказательство можно найти в [ХопМот, 9.4].

Упражнение 14.5.8. Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.9. Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.10. Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.11. Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.12. Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.13. Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.14. Существует ли решение у постовской системы соответствия ?

Упражнение 14.5.15. Существует ли постовская система соответствия, имеющая ровно одно решение?

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

Первые два раздела этой лекции посвящены контекстным языкам. В разделах 15.3-15.6 сформулированы теоремы о разрешимости для некоторых алгоритмических проблем. Доказательства этих теорем опираются на конструктивность рассуждений, проведенных в лекциях "3" и "8". В разделе 15.7* приводится новый неожиданный результат, доказанный в 1997 году.

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

Неукорачивающие грамматики

Определение 15.1.1. Порождающая грамматика называется неукорачивающей (noncontracting), если для каждого правила выполняется неравенство .

Теорема 15.1.2. Существует алгоритм, позволяющий по произвольной неукорачивающей грамматике G и по слову wузнать, верно ли, что .

Теорема 15.1.3. Каждая контекстная грамматика является неукорачивающей. Каждая неукорачивающая грамматика эквивалентна некоторой контекстной грамматике.

Пример 15.1.4. Грамматика

эквивалентна контекстной грамматике из примера 1.5.4.

Упражнение 15.1.5. Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.6. Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.7. Найти неукорачивающую грамматику, порождающую язык .

Упражнение 15.1.7. Найти неукорачивающую грамматику, порождающую язык .

15.2*. Линейно ограниченные автоматы

Определение 15.2.1. Машина Тьюринга

называется линейно ограниченным автоматом (linear bounded automaton), если не существует таких , , , и , что и |xay| > |b₀wb₀|.

Теорема 15.2.2. Язык L, не содержащий пустого слова, порождается некоторой неукорачивающей грамматикой тогда и только тогда, когда существует линейно ограниченный автомат (в общем случае недетерминированный), допускающий язык L.

Замечание 15.2.3. Неизвестно, верен ли аналог теоремы 15.2.2 для детерминированных линейно ограниченных автоматов.

Теорема 15.2.4. Класс языков, порождаемых неукорачивающими грамматиками, то есть класс контекстных языков, замкнут относительно операций объединения, пересечения и дополнения.

Замкнутость относительно операции дополнения доказали в 1987 году (независимо друг от друга) Нил Иммерман (Neil Immerman) и Роберт Селепчени (Robert Szelepcs) (см. [Imm, Sze]). Замкнутость относительно операции объединения очевидна, а пересечение выражается через объединение и дополнение.

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

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

Проблема выводимости слова

Теорема 15.3.1. Существует алгоритм, позволяющий по произвольной контекстно-свободной грамматике G узнать, верно ли, что .

Теорема 15.3.2. Существует алгоритм, позволяющий по произвольной контекстно-свободной грамматике G и по слову w узнать, верно ли, что .

Упражнение 15.3.3. Принадлежит ли слово aaaaabbbabb языку, порождаемому грамматикой

Упражнение 15.3.4. Принадлежит ли слово abababa языку, порождаемому грамматикой

Проблема пустоты языка

Теорема 15.4.1. Существует алгоритм, позволяющий по произвольной контекстно-свободной грамматике G узнать, верно ли, что .

Доказательство. Удалим из G все бесполезные символы, кроме начального символа (как в доказательстве теоремы 8.1.3). Если полученная грамматика содержит хотя бы одно правило, то .

Упражнение 15.4.2. Является ли непустым язык, порождаемый грамматикой