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


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

370 Добавление к статье Касами
будут использованы следующие формулы: >0= V
(D
,0 = V [мф(1, / -1) л мл (/,*)]. (1)
К / < i
Сигнал MA(j, i) известен, если уже построено множество N(j,i)\ в алгоритме Касами это происходит во время г'-го пробега машины. Заметим, что к этому моменту уже построены все множества N(IJ — 1), где 1 Предлагаемый ниже алгоритм позволяет за время 1-го пробега машины найти все множества M Переорганизуем машину, распознающую линейные языки, следующим образом:
1. В блок состояний добавляем еще одну рабочую ячейку М3. Эта ячейка имеет q + 1 разряд, где q — мощность множества Ф; по одному разряду предназначено для хранения ф е Ф, и один — для выходного сигнала. Во время i-ro пробега машины каждый разряд М3 действует как накопитель: вновь пришедший сигнал логически суммируется с содержимым разряда. За время t'-ro пробега в ячейке А13 по формулам (1) постепенно формируются сигналы Мф(1,г) и Ms(l,i).
2. В каждый блок ленты, содержащий входной символ а^ (/>!), добавим q разрядов для хранения сигналов Мф(1,/ — 1) (ф е Ф). Таким образом, /-и блок на ленте (1 МФ1(1,/-П Мф2(1, /-1) Мф (1,7-1) VQ ul N а о
Алгоритм распознавания металинейного языка работает так:
Первый шаг. Первый ,шаг работы машины начинается так же, как и для линейного языка, а именно машина считывает первый входной символ «i и строит множество Л/(1, 1). Затем символы из N(lt 1) проверяются на принадлежность к Q и к Ф; сигналы Ма,(1, 1) засылаются в разряд ячейки М3, предназначенный для выходного сигнала, а сигналы Мф(1, 1)—в предназначенные для них разряды М3. Легко видеть, что после этой операции в Л43 окажутся правильно сформированные выходной сигнал Ms(l, 1) и все символы М^(\, 1) (заметим, что для более чем однобуквенной цепочки ф всегда M(f(l, 1) = 0, поскольку в грамматике G из длинной цепочки ф нельзя получить более ко-

 

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 350 360 370 371 372 373 374 375 376 377 378 379 380 390 400 410 420 430


Математика