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


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

350 Д. X. Янгер
б) если вычислены элементы матрицы для всех I' < t, где 1, то
(суммирова-ние логическое), (4)
где Ph — множество упорядоченных пар (k\, k2), таких, что Ak— > Ak^Akt — правило G. Другими словами, эта логическая сумма означает, что r(i, /, k) — 1, если для некоторого правила Ak-+ AkiAkz из G и некоторого t между 1 и i — 1 предварительно вычисленные значения r(t,j,k\) и r(i — /, / + t, k2) оба равны 1; > /» &) = 0 в противном случае.
Доказательство правильности итеративного процесса. Предположим, что процедура вычисляет элементы матрицы распознавания в соответствии с определением для всех t < to. Чтобы определение удовлетворялось при t = to, r(i^j,k) должно быть равно 1 только в случае, когда Ak=^SjSj+\ . ..s/+/r_i. Это заведомо верно при t'o = 1; для to > 1 это выполняется в том и только в том случае, когда существует такое значение индекса t между 1 и t'o—1, что для некоторого правила Ak-+Ak{Ak2 нормальной грамматики выполняется Ak^s/sj+i... s/+*-i и Ak^Sj+tSj+t+i...
.. . s/+/0-i. Последняя пара отношений может выполняться тогда и только тогда, когда r(t,j,ki) = 1 и г (t'o — t, j + t, &2) = 1 no предположению индукции. Другими словами, r(i0tjtk) = 1 тогда и только тогда, когда логическая сумма (4) для t = /0 равна 1. Пока мы вычисляем матрицу распознавания вручную, нас вполне устраивает запись правил грамматики в виде, аналогичном (2); при автоматическом вычислении требуется форма, в большей степени соответствующая этому случаю. По аналогии с матрицей распознавания представим грамматику в форме двоичной матрицы. Здесь нужны, однако, две матрицы: одна — для терминальных правил, а другая — для двойных. Терминальные правила представляются упорядоченной парой символов каждое: первый — символ нетерминальный, второй — терминальный. Правила можно представить в виде двоичной матрицы
G. —— I rf . { г? /II t Ls t \ > /jCisy
где q — число нетерминальных символов, а 5 — число терминальных символов в словаре. Элемент gt(kt /) = 1, если Ah-+a,i — терминальное правило G, и gt(kt /) = 0 в противном случае. Двойные правила суть упорядоченные тройки символов из N. Их можно представить в виде матрицы Ge = [#с(&, &ь ^2)]qqq. Элементы

 

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 351 352 353 354 355 356 357 358 359 360 370 380 390 400 410 420 430


Математика