Математическая теория формальных языков

       

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


Определение 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 в виде слова. Например, можно использовать алфавит , где - дополнительные символы, не принадлежащие множеству . Вспомогательный символ Ai

заменим на слово, состоящее из символа

и кода числа i в двоичной системе счисления. В каждом правиле

добавим символ

на месте

и после слова . Кодом грамматики G будем считать результат конкатенации кодов всех правил из множества P. Например, грамматика

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

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

Упражнение 14.3.8.

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



Содержание раздела