Загрузка...

О разрешимости проблемы пустоты КС языка.


Если — КС грамматика, то разрешима проблема пустоты языка .

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

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

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

ТЕОРЕМА 1.7. О разрешимости языков, заданных контекстными грамматиками.
Если грамматика — контекстная, неукорачивающая грамматика, то язык разрешим.

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

ТЕОРЕМА 1.8. О неукорачивающих грамматиках.
Если грамматика — неукорачивающая, то есть продукции грамматики имеют вид , то существует эквивалентная ей контекстная грамматика .

Если грамматика — неукорачивающая, то в соответствии с теоремами 1.7 и 1.8 язык , порожденный этой грамматикой, разрешим.

Загрузка...