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


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

360 Л X. Япгер
8. УНИВЕРСАЛЬНАЯ МАШИНА ДЛЯ РАСПОЗНАВАНИЯ И АНАЛИЗА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ
Теперь расчленим управляющее устройство G-машины. Оно состоит из управляющего устройства (У-машины (U означает универсальность) и двух лент. Другими словами, добавив две ленты для работы с грамматикой и изменив управляющее устройство, мы можем создать (/-машину, которая будет выполнять распознавание для любой контекстно-свободной грамматики в нормальной форме. Одна из дополнительных лент — входная; на ней записана грамматика в виде трех массивов, разделенных одиночными пустыми квадратами. Первый массив — цепочка единиц длины q — число нетерминальных символов нормальной грамматики. Второй массив — это терминальные правила грамматики. Он занимает qs квадратов (s — число терминальных символов). Квадрат, отстоящий на (/ — \)q + k квадратов от ближайшего левого пустого квадрата, содержит 1, тогда и только тогда, когда Ah-*ai есть терминальное правило, и 0 в противном случае. Третий массив занят двойными правилами грамматики и занимает q3 квадратов. Здесь квадрат, отстоящий на (k — 1)<72 + (k\ — \)q + k2 квадратов от ближайшего левого пустого квадрата, содержит 1, если Л, ь — > A k[Ak2 — двойное правило грамматики, и 0 в противном случае. Вид входной ленты выбран в соответствии с формой записи матрицы распознавания на ленте.
Вторая добавочная лента — это рабочая лента, на которой хранятся записи параметров грамматики, т. е. q, k, &ь &2-
Теперь мы можем сосчитать число шагов, необходимое для распознавания (/-машине. Оно оказывается похожим на ранее
полученную величину, именно -j-q3n?. Теперь мы, однако, должны
учесть число шагов, требуемое для вычисления плоскости i = 1, для возвращения рабочих и читающих головок в исходные положения, для записи двух дополнительных копий матрицы распознавания. Все это увеличивает время распознавания. Не вдаваясь в подробности, скажем только, что для вычисления плоскости i = 1 нужно не более, чем (2s + \)qn шагов, для остальных
элементов — не более чем -5-/г3( При q> I, qn^> s получаем
7V = j"V> (13)
где TV — обозначает верхнюю границу времени распознавания.

 

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 361 362 363 364 365 366 367 368 369 370 380 390 400 410 420 430


Математика