Математическая логика и теория алгоритмов. Анкудинов Г.И - 66 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

приписывает *f (X) в конце записи f
2 1
(X) на нижнем этаже и стирает
f
(X) на верхнем этаже.
2
Ветвление программ. Пусть машины M
и M
1 2
вычисляют
словарные функции f
(X) и f
1 2
(X) соответственно в одном и том же
алфавите A. Введем символы и (истина) и л (ложь), причем и∉A и
л∉A. Построим машину M= M
∨
1
M
2
, которая преобразует слово σ*X,
где σ∈{и,л}, в слово f
(X), если σ=и, и в слово f
1 2
(X), если σ=л
(рис.4.3). Для этого, полагая что алфавиты состояний M
и M
1 2
различны, в основу M положим объединение их программы. Введем
для M начальное состояние q
и, полагая, что q и q
1 1,1 2,1
– начальные
состояния M
и M
1 2
соответственно, дополним
объединение программ M
X
f
2
f
2
(
X
)
f
1
(X) f
1
и
л
σ
Рис.4.3.
1
и
M
2
командами
иq
→ ΛПq ,
1 1,1
→ ΛПq
лq
,
1 2,1
→ ΛПq
*q
,
1,1 1,1
→ ΛПq
*q
.
2,1 2,1
Заключительные состояния q
и q машин M и M
1,0 2,0 1 2
обозначим как
заключительное состояние q
машины M= M
0 1
∨M .
2
Машину M= M
1
∨M можно представить схемой на рис.4.4.
2
f
1
(X)
σ=и
σ*X
M
1
∨
M
2
f
2
(X)
σ=л
Рис.4.4.
150

Страницы