И.В. Рудаков
4
2. Для любых последовательностей
ε
r
P
и
ε
t
P
из
ε
P
и любого
v
, где
1 ≤
v
≤ min(
r
,
t
), если
ε = ε
P
P
r v
t v
J
J
, то
(
)
(
)
ε = ε
P
P
r v
t v
H J H J
где
ε
P
r v
J
— начало последовательности
ε
P
r
длиной
v
.
Определенная таким образом функция
H
является последова-
тельностно-детерминированной функцией, и для нее каноническая
система уравнений имеет вид:
(
)
1 2
1 2
, , , , ,
= , , , , ,
Q Q
Q
Q
P P
P
P
v
r
v
r
e e
e
e H e e
e
e
K K
K K
.
Для последовательностной детерминированной функции
H
вве-
дем
K
— множество чисел, которыми занумерованы состояния функ-
ции
H
, т. е.:
1 2 3
: = { , , , }
H K k k k
K
.
Детерминированная последовательностная функция
H
может
быть представлена соотношениями:
(
)
(
)
(1) = ,
( 1) = ( ),
,
= ψ ( ),
,
v
P
w
Q
P
w
w
k
k
k w
k w e
e
k w e
⎧
⎪⎪ + φ
⎨
⎪
⎪⎩
(1)
где
:
ε
P
K K
φ ⋅
→
;
ψ :
ε ε
P
Q
K
× →
;
k
(1) — начальное состояние
функции
H
;
k
(
w
) — состояние функции
H
на шаге с номером
w
;
P
w
e
— входная буква функции
H
на шаге с номером
w
;
Q
w
e
— выход-
ная буква функции
H
на шаге с номером
w
.
Входы схемы
S
занумеруем следующим образом:
1 2 3
, , , , , ,
p
n
i i i
i
i
K K
где
i
p
— номер
p
-го входа схемы
S
.
Припишем входам схемы
S
переменные из множества
X
, самой
схеме — последовательностную детерминированную функцию
H
. В
этом случае, если на вход
S
подавать буквы последовательности
ε ,
P
r
то на выходе
S
устанавливается последовательность выходных букв
ε
Q
r
, причем
( )
ε = ε
Q
P
r
r
H
. Работа схемы
S
заключается в следующем: в
определенные моменты на вход схемы
S
поступают входные буквы
ε
P P
r
e
∈
; схема
S
находится в одном из внутренних состояний, коди-
