Загрузка...

НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ ДЛЯ ГРАММАТИКИ.


Определение. НЕРАЗРЕШИМОЙ ПРОБЛЕМОЙ называется отсутствие эффективной процедуры решения некоторой задачи для наперед неизвестной грамматики .
Основным методом доказательства неразрешимостей в теории формальных систем является сведение задачи к комбинаторной проблеме Поста.

ЛЕМА 1.9. О комбинаторной проблеме Поста.
Комбинаторная проблема Поста неразрешима. Для двух различных списков строк
длины , в алфавите , при достаточно больших существует ли последовательность индексов конечной длины такая, что : эти строки равны – является неразрешимой проблемой.

ДОКАЗАТЕЛЬСТВО.
A. Неразрешимость означает, что для наперед нам неизвестных список строк не существует эффективной процедуры, которая за конечное число шагов и при конечной памяти может построить последовательность индексов конечной длины.
Пример. Пусть есть два списка строк

Проиндексируем члены этих списков и возьмем в качестве строк строки, индекс
Которых равен 3. и . Выберем строки с индексами 3 и 1 и объединим с помощью операции конкатенации эти строки. Получим . Выберем строки с индексами 3 и 2. Получим Строки и не равны, следовательно, проблема Поста не разрешима.

B. Докажем утверждение леммы 1.9 в общем случае.
Число строк вида счетно. Эти множества являются множествами строк конечной длины в конечном алфавите, длины этих строк определяются конечной последовательностью индексов . Отсюда заключаем, что для решения комбинаторной проблемы Поста необходимо выбрать и сравнить сответствующие строки из двух счетных множеств, порожденных списками и .
C. Так как списки и наперед неизвестны, то есть не заданы, то гарантировать, что за конечное число шагов будут найдены совпадающие строки невозможно.
Окончание доказательства.

ЛЕММА 1.10. Комбинаторная проблема Поста для КС языков, порожденных списками строк.
Если — списки строк конечной длины в алфавите , то комбинаторная проблема Поста для этих списков имеет решение. То есть, если языки , где — это КС языки, включающие всевозможные строки вида , где , , здесь — знаки терминального алфавита , состоящего из знаков .

ДОКАЗАТЕЛЬСТВО.
A. Пусть строка принадлежит языку и , тогда то есть , то есть построена последовательность индексов для произвольных списков строк .Но языки и не пересекаются.
B. Покажем, что языки и порождяются КС грамматикой , где — КС грамматики. Для этого построим продукции грамматики следующего вида , , очевидно, что эти граматики контекстно – свободные и порождают языки и соответственно.
C. Грамматики , являются однозначными, то есть для каждой строки языка существует единственная последовательность ее вывода.
Окончание доказательства.

Загрузка...