Математическая теория формальных языков
Массовые задачи
Определение 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}?
