Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 37

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 31 32 33 34 35 36 < 37 > 38 39 40 41 42 43 .. 104 >> Следующая

Замечание. При составлении операторной схемы важно, чтобы заключительное положение головки после выполнения очередного оператора совпадало с начальным положением следующего оператора. Иногда для этого приходится вводить дополнительные согласующие операторы.
В нашем примере согласование получается естественным образом, кроме оператора р{а'а"), для которого мы считаем, что после его выполнения головка встает над а,
III эт ап. Переход от операторной схемы к программе машины.
Сначала составляют программы для каждого из операторов данной операторной схемы (кроме операторов *, Ръ <*>)..
126 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Продолжение примера 5. Мы имеем следующие программы для операторов, входящих в схему (если операторы встречаются в схеме несколько раз, то программу составляем для одного из них; см. табл. С).
Таблица О
*1
0 1 15хд
0(сг') *3
0 1 и Ах,
А| х2 У.,
0 1 \Нщ 0/|’х}
А; х»
0 1 иДх0
р(а'а") X4 х5 X;
0 0Ьх;
1 1/?хй 1 Ьх„
Ф<1* — и-1) Хю X,,
0 1 1Ахп 1/?х10
Ь X X
и 1 о/и" 1/„х’
При написании программ для операторов состояния выбираем так, чтобы множества состояний для разных операторов не пересекались.
Далее, операторную схему можно рассматривать как схему, определяющую композицию программ (машин). Для этого сначала «оборвем» все стрелки (кроме стрелок тина1). Будем считать, что каждый конец стрелки ведег к своему состоянию останова.
И примере 5 получим следующую схему:
*Ф(0*^1*)Л,р(а#йда),0(а,)^8Ф(11-> 111)р0;0(а/)Ла1м.
Затем, беря фрагмент этой схемы
А,р{а'а")Ю(а')/и Ф(1*-М1*),
строим программу, являющуюся последовательным подключением соответствующих программ. После этого переходим к фрагменту
| А1Р(а'а")'0 (а') АЛФ (1^ II1) р0 [
и строим программу, применяя операцию итерации к предыдущей программе относительно предиката Далее, берем фрагмент
* Ф (О1-»-!1) ^ А} р {а1 а-)1 0 {а') Л2Ф(1Т^ II1) рс (
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ 127
и по нему строим программу, беря последовательное подключение предыдущей программы к программе для Ф(04 -*? I4). И, паконец, вся схема
* ф (о1 -> 11)| Ахр (а’а”)10 (а1) Л2Ф ( {1 Й1) Ри (О (о') АгЫ
приводит к программе, являющейся последовательным подключением могтроештой программы и программ для
Таблица 7
ф(01 —)!) р(а'а'‘) О(а')
к, П.; х* У-Ь х« X?
О Т-. | !.?К1 0/?х3 1Л’к4 1 Пхъ 07, х7 1Лхг> ОУхр 0 5хи Об'*,, 05х8
Л2 ФП'1— Ы) 0(гГ> А, Ь й)
X* ?''?10 ч. ки ^13 Х14 х16
0 1 0/,х(1 15Кц 1Ях1п 0Ух2 1 5к2 0 Яу.а 0.9и12 01х13 1?к14 0/?х1Й 1ЙХИ
О (а'), А а и Ь. Окончательный вид этой программы дан в табл. V.
Замечание. При последовательном подключении программ, соответствующих двум соседним операторам В' и В" операторной схемы, образующим фрагмент В'В", предикат р полагается равным тождественно 1, если оператор В' является оператором, преобразующим запись ленты, состояния машины и положения головки. Если В' есть оператор проверки логического условия, то выбор предиката р согласуется с этим логическим условием.
IV этап. Упрощение программы. Построенные данным методом программы иногда допускают значительное упрощение по числу состояний. Здесь мы сформулируем некоторые принципы упрощений.
Допустим, что программа имеет два состояиия у/ и к" таких, что соответствующие им столбцы имеют пустые
(28 Ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
клетки, в которые машина никогда не попадает. Пусть для каждой строки существует пустая клетка данного вида (по крайней мере в одпом из указанных столбцов). Легко видеть, что тогда можно состояния х' и и" отождествить.
Другой тип упрощений связан с операторами проверки логических условий. Мы поясним его на нашем примере.
Продолжение примера 5. Состояния хв и у-ч связаны с командами, которые осуществляют только переходы к другим состояниям. Их мож-
Таблица 8 но исключить, скорректировав' команды для х5.
Еще одна возможность упрощений связана с командами, содержащими символ движения 5. Пусть в клетке (с, х) находится команда с'Вк*. Тогда, если к этой команде можно непосредственно перейти только от команд с5х, и она не работает в начальный момепт, то команду с'Вх,' в клетке (с, х) можно изъять, а все команды с5х заменить на с'Пх'.
Продолжение примера 5. В программе из табл. 7 к команде 15кг, находящейся в клетке (1, «О, можно непосредственно попасть только из команды 15х|
Таблица 9
X, х« хв Хц> >1* X)» *14
0 1 1<5х! 1Яия (Ши, 1 Яу-ь 0 ЬЩъ 1 Ьх9 0Ух9 ОУх* 0 /,хв 1ЯХ, 1ЯК1П 0Ухг5 0?х1Ч 15хм ОХЩь 1?к,4
того же столбца. Поэтому первый столбец программы может быть заменен на следующий (см. табл. 8). После этого можно отождествить состояния X* и х2, так как в ячейках (1, х,) и (0, х2) стоят пустые команды и в них машина никогда не попадает.
Аналогичное преобразование можно проделать со столбцами для х* и х4: изъять команду 1йх5 и отождествить состояния х3 и х4. Наконец, в столбце х« команда 05х2 никогда не работает и ее можно изъять, а 15хг можно
ГЛ. 4. ВЫЧИСЛИМЫЕ ФУНКЦИИ 129
также изъять, внеся необходимые изменения в столбец для к».
Мы приходим к программе (см. табл. 9), содержащей 10 состояний.
Предыдущая << 1 .. 31 32 33 34 35 36 < 37 > 38 39 40 41 42 43 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed