Составители:
Рубрика:
Пример 4.3. Сложение. В таблице 4.3 приведен пример программы
машины с алфавитом состояний {q
,q ,q ,q }.
1 2 3 0
Таблица 4.3
q a
q q q
q
1 2 3 4
Λ
ΛПq 1Лq ΛНq
ΛПq
1 1 2 0
1
1Лq 1Пq ΛПq
ΛПq
3 2 3 0
+
+Лq +Пq ΛНq
ΛПq
4 2 3 0
Например, сложение чисел 11+111 (один плюс два) осуществляется за
два цикла. Начальное состояние головки q
. Состояние q
1 3
поддерживает
перемещение головки вправо с одновременным "перетаскиванием" единицы:
…Λq
11+111ΛΛΛ…⇒ …ΛΛq 1+111ΛΛΛ…⇒ …ΛΛ1q
1 3 3
+111ΛΛΛ…⇒
…ΛΛ1+q
111ΛΛΛ…⇒ …ΛΛ1+1q 11ΛΛΛ…⇒ …ΛΛ1+11q 1ΛΛΛ…⇒
3 3 3
ΛΛΛ…⇒ …ΛΛ1+11q
…ΛΛ1+111q
11ΛΛ… .
3 2
Состояние q
соответствует перемещению головки влево:
2
11ΛΛ…⇒ …ΛΛ1+1q 111ΛΛ…⇒ …ΛΛ1+q
ΛΛ1+11q
2 2 2
1111ΛΛ…⇒
…ΛΛ1q
+1111ΛΛ…⇒ …ΛΛq 1+1111ΛΛ…⇒ …Λq Λ1+1111ΛΛ…⇒
2 2 2
…ΛΛ q
1+1111ΛΛ… .
1
Первый цикл закончен. Второй цикл:
…ΛΛ q
1+1111ΛΛ…⇒ …ΛΛΛq +1111ΛΛ…⇒ …ΛΛΛ+q 1111ΛΛ…⇒
1 3 3
. . .
…ΛΛΛ+ 1111q
ΛΛ…⇒ … ΛΛΛ+ 111q 11Λ…⇒ …ΛΛΛ+ 11q 111Λ…⇒
3 2 2
. . .
…ΛΛq
Λ+ 11111Λ…⇒ …ΛΛΛq + 11111Λ… .
2 1
Второй цикл закончен. Машина удаляет лишнюю единицу
…ΛΛΛq
+ 11111Λ…⇒ …ΛΛΛΛq 11111Λ …⇒ …ΛΛΛΛq 1111Λ…
1 4 0
и, достигнув состояния q
0
, останавливается. Конфигурация
…ΛΛΛΛq
11111Λ… дает решение задачи.
0
Пример 4.4. Усеченное вычитание. В таблице 4.4 приведен пример
программы вычисления усеченной разности.
Таблица 4.4
a q
147
Страницы
- « первая
- ‹ предыдущая
- …
- 61
- 62
- 63
- 64
- 65
- …
- следующая ›
- последняя »
