Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

340 $ж Хартманис
от друга функциями памяти L(n), расположенными между [log log /г] и [log n]. (Неизвестно, требуется ли для распознавания какого-либо бесконтекстного языка объем памяти более чем [log л].)
Таким образом, доказано, что распознавание нерегулярных бесконтекстных языков может требовать резко различных объемов памяти, которые занимают экспоненциальную шкалу от L(n) = [log log п] до L (n) = [log n]. Далее, известно, что невозможно эффективно узнать, когда бесконтекстная грамматика порождает регулярный язык [2], и, следовательно, неразрешим ъспрос о том, распознаваем ли некоторый язык с конечной длиной ленты.
Ниже доказывается, что если даже заранее известно, что язык нерегулярен, то вопрос о длине ленты, необходимой для его распознавания, остается алгоритмически неразрешимым. Как и многие другие доказательства неразрешимости различных свойств бесконтекстных языков, это доказательство опирается на неразрешимость комбинаторной проблемы Поста [2, З]1).
ТЕОРЕМА О НЕРАЗРЕШИМОСТИ
Вначале построим два хорошо известных вспомогательных языка, используемых в доказательстве теоремы о неразрешимости. Пусть А и В — два списка, т. е. два упорядоченных набора из k непустых бинарных последовательностей
где fc^-1, аг-, bi из {О, 1}*, и пусть i означает двоичную запись числа /. Тогда полагаем по определению
L (Л) = {ii * 12 * ... * ip * * aip . . . а и аналогично
Языки L(A) и L(B) могут распознаваться детерминированным автоматом PDS и, следовательно, являются бесконтекстными
языками; их дополнения L(A) и L(B) также бесконтекстны [2]. Лемма 1. Если
!) См. также Марков А. А., Теория алгорифмов, Труды МИАН, т. 42. гл. VI, § 9, 1954, и М а л ь и е в А. И., Алгоритмы и рекурсивные функции, М., 1965, стр. 301. — Прим, перев.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 341 342 343 344 345 346 347 348 349 350 360 370 380 390 400 410 420 430


Математика