РАЗРЕШИМОСТЬ ЯЗЫКОВ


Под РАЗРЕШИМОСТЬЮ ЯЗЫКОВ понимается распознавание принадлежности произвольной строки языку, заданному формальной грамматикой .

ТЕОРЕМА 1.4. О разрешимости КС языков.
Если КС грамматика, то разрешима проблема определения принадлежнос-ти произвольной строки в терминалном алфавите языку , порожденному этой грамматикой.

ДОКАЗАТЕЛСТВО.
A. Рассмотрим КС грамматику продукции которой имеют вид , где . Рассмотрим систему множеств таких, что , которые состоят из терминальных строк, выводимых из знака в КС грамматике .
B. Введем операции над множествами .
1. Конкатенация множеств .
2. Объединение множеств .

Свойства операции над множествами .
1. Некоммутативность конкатенации .
2. Коммутативность объединения .
3. Неидемпотентность конкатенации .
4. Идемпотентность объединения .
5. Ассоциативность конкатенации и объединения , .
6. Дистрибутивность объединения относительно конкатенации .

7. Действия с универсальным, пустым множествами и множеством, состоящим из пустой строки , .
C. Рассмотрим систему уравнений относительно введенных множеств в КС грамматике

Систему уравнений составим по следующим правилам: Если в множестве продукций КС грамматики существует группа продукций с терминальным знаком вида , где представим как конкатенацию нетерминальных и терминальных знаков
, тогда получим уравнение , в котором
Пример: Если в множестве продукций КС грамматики есть продукция , то уравнение для имее вид .
Замечание. При выводе уравнения учтено, что , то есть конкатенация множеств, состояших из одного знака есть множество, включающее единственную строку, равную конкатенации знаков этих множеств (следует из свойств операции конкатенации).
D. Найдем решение системы уравнений , где — вектор множеств с числом компонентов равным числу нетерминальных знаков.

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

Получим решение системы уравнений .
Пусть решение системы будет . Тогда . Известно, что , тогда . Продолжая далее получим . Следовательно, решением уравнения является

Замечание. Множество строк принадлежащих языку находится в множестве . Все остальные множества являются вспомо-гательными для построения множества

E. Приведем эффективную процедуру определения принадлежности строки языку , порожденному КС грамматикой .
Шаг 1. Строим систему уравнений как это было описано в пункте С.
Шаг 2. Задаем начальное приближение решения системы уравнений .

Шаг i. Пусть имеется частное решение системы уравнений

Шаг i+1. Строим следующее приближение решения систем уравнений в виде

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

Замечание. Действительно, если при выводе в КС грамматике получена синтенциальная форма, состоящая из нетерминальных знаков и терминальных подстрок , которая приводит к строке , то является подстрокой строки .

Шаг k. Завершаем процедуру на этом шаге, если , то есть является строкой языка, или, когда (в этом случае строка не принадлежит языку).
F. Так как число уравнений n в системе уравнений конечно и длина строки ограничено и равно ,то решение поставленной задачи о разрешимости КС языка для произвольной строки получаем не более чем за шагов. Это утверждение основано на том, что КС грамматика является неукорачивающей и при проведении иттераций длины строк растут. Таким образом проблема принадлежности произвольной строки языку разрешима.
Окончание доказательства.

Пример. Определить, принадлежит ли строка языку , порожденному КС грамматикой .

Применим эффективную процедуру определения принадлежности строки языку порожденному КС грамматикой .
Шаг 1. Строим систему уравнений относительно множеств , где содержит терминальные строки, выводимые из знака .
Шаг 2. Задаем начальное приближение решения системы уравнений
Шаг 3. Находим следующее приближение системы уравнений

Удаляем из полученного множества те строки, которые не являются подстроками исходной строки .
Шаг 4. Повторяем шаг 3 до тех пор, пока искомая строка не появится в множестве , или система множеств на текущем шаге итерации не совпадет с системой множеств на предыдущем шаге итерации (строка не принадлежит языку .
A)
B)
C)
Строка принадлежит языку , порожденному КС грамматикой .