Словесное описание алгоритма
Определяем тип первого элемента: если он равен «Н», сдвигаем головку вправо, ищем элементы «0» и «1» и заносим их в 9 ленту.
Ищем элемент «*», после определения сдвигаем ленту вправо, переходим на 5 ленту, и там также ищем элементы «0» и «1» и затем заносим их в 9 ленту для получения сложения первых элементов матриц.
Выполняем операции пункта 1 и 2 со 2-ой и 6-ой лентой соответственно и заносим «0» и «1» в 10-ую ленту в зависимости от того, что считали в этих лентах, а затем с 3-ей и 7-ой в 11-ю ленту, 4-ой и 8-ой в 12-ю ленту.
Завершение работы алгоритма.
Внешний алфавит
А = {Н, 0, 1, *, К}
Н - начало ленты
0 – символ “0”
1 - символ “1”
* - символ перехода
К – конец ленты
Внутренние состояния
Q = {q0, q1, q2, q3, …, q25, q26, q27, E}
Внутреннее состояние |
Описание |
q0 |
просмотр 1 ленты |
q1 |
“0” в 9-ю ленту из 1-ой |
q2 |
“1” в 9-ю ленту из 1-ой |
q3 |
просмотр 5 ленты |
q4 |
“0” в 9-ю ленту из 5-ой |
q5 |
“1” в 9-ю ленту из 5-ой |
q6 |
просмотр 9 ленты |
q7 |
просмотр 2 ленты |
q8 |
“0” в 10-ю ленту из 2-ой |
q9 |
“1” в 10-ю ленту из 2-ой |
q10 |
просмотр 6 ленты |
q11 |
“0” в 10-ю ленту из 6-ой |
q12 |
“1” в 10-ю ленту из 6-ой |
q13 |
просмотр 10 ленты |
q14 |
просмотр 3 ленты |
q15 |
“0” в 11-ю ленту из 3-ой |
q16 |
“1” в 11-ю ленту из 3-ой |
q17 |
просмотр 7 ленты |
q18 |
“0” в 11-ю ленту из 7-ой |
q19 |
“1” в 11-ю ленту из 7-ой |
q20 |
просмотр 11 ленты |
q21 |
просмотр 4 ленты |
q22 |
“0” в 12-ю ленту из 4-ой |
q23 |
“1” в 12-ю ленту из 4-ой |
q24 |
просмотр 8 ленты |
q25 |
“0” в 12-ю ленту из 8-ой |
q26 |
“1” в 12-ю ленту из 8-ой |
q27 |
просмотр 12 ленты |
Е |
Конечное состояние |
Система команд
|
Н |
0 |
1 |
* |
К |
q0 |
q0 H R |
q1 0 R |
q2 1 R |
q3 * R |
q7 K L |
q1 |
|
q0 0 R |
|
|
|
q2 |
|
|
q0 1 R |
|
|
q3 |
q3 H R |
q4 0 R |
q5 1 R |
q6 * R |
|
q4 |
|
q3 0 R |
|
|
|
q5 |
|
|
q3 1 R |
|
|
q6 |
|
|
|
q0 * R |
|
q7 |
q7 H R |
q8 0 R |
q9 1 R |
q10 * R |
q14 K L |
q8 |
|
q7 0 R |
|
|
|
q9 |
|
|
q7 1 R |
|
|
q10 |
q10 H R |
q11 0 R |
q12 1 R |
q13 * R |
|
q11 |
|
q10 0 R |
|
|
|
q12 |
|
|
q10 1 R |
|
|
q13 |
|
|
|
q7 * R |
|
q14 |
q14 H R |
q15 0 R |
q16 1 R |
q17 * R |
q21 K L |
q15 |
|
q14 0 R |
|
|
|
q16 |
|
|
q14 1 R |
|
|
q17 |
q17 H R |
q18 0 R |
q19 1 R |
q20 * R |
|
q18 |
|
q17 0 R |
|
|
|
q19 |
|
|
q17 1 R |
|
|
q20 |
|
|
|
q14 * R |
|
q21 |
q21 H R |
q22 0 R |
q23 1 R |
q24 * R |
E |
q22 |
|
q21 0 R |
|
|
|
q23 |
|
|
q21 1 R |
|
|
q24 |
q24 H R |
q25 0 R |
q26 1 R |
q27 * R |
|
q25 |
|
q24 0 R |
|
|
|
q26 |
|
|
q24 1 R |
|
|
q27 |
|
|
|
q21 * R |
|