3.2 Generation of Finite Automata with Invertibility 93
Lemma 3.2.3. Assume that eq
0
(i) is
r
j=0
G
j0
(y(i, t +1))ψ
l
μν
(u(i − j, μ +1),x(i − j, ν +1))=0
and G
0
(i)=[G
00
(y(i, t+1)),...,G
τ0
(y(i, t+1))], τ r. For any m×l(τ +1)
(l, τ)-echelon matrix G
τ
(i) over R[y
i+τ
,...,y
i−t
],if
G
k+1
(i)
R
−1
b
[r
k+1
]
−→ G
k
(i),G
k
(i)
R
−1
a
[P
k
]
−→ G
k
(i),k= τ − 1,...,1, 0 (3.9)
is an R
−1
a
R
−1
b
transformation sequence, then
eq
k
(i)
R
a
[P
k
]
−→ eq
k
(i),eq
k
(i)
R
b
[r
k+1
]
−→ eq
k+1
(i),k=0, 1,...,τ − 1 (3.10)
is an R
a
R
b
transformation sequence and the first l columns of G
τ
(i) and
the first l columns of the coefficient matrix of eq
τ
(i) are the same, where
P
k
(y(i + k, k + t +1))=(P
k
(y(i + k, k + t + 1)))
−1
, 0 k<τ.
Proof. Assume that (3.9) is an R
−1
a
R
−1
b
transformation sequence. From
Lemma 3.2.2,
G
k
(i)
R
a
[P
k
]
−→ G
k
(i),G
k
(i)
R
b
[r
k+1
]
−→ G
k+1
(i),k=0, 1,...,τ − 1
is a modified R
a
R
b
transformation sequence. From Lemma 3.2.1, (3.10) is
an R
a
R
b
transformation sequence, and the first l columns of G
τ
(i)andthe
first l columns of the coefficient matrix of eq
τ
(i)arethesame.
Theorem 3.2.1. Let f and g be two single-valued mappings from Y
t
×
U
p+1
× X
r+1
to Y and U, respectively. Let M = X, Y, Y
t
× U
p+1
× X
r
,δ,λ
be a finite automaton defined by
δ(y(i − 1,t),u(i, p +1),x(i − 1,r),x
i
)
= y(i, t),u(i +1,p+1),x(i, r),
λ(y(i − 1,t),u(i, p +1),x(i − 1,r),x
i
)=y
i
,
where
y
i
= f(y(i − 1,t),u(i, p +1),x(i, r +1)),
u
i+1
= g(y(i − 1,t),u(i, p +1),x(i, r +1)).
Let eq
0
(i) be the equation
−y
i
+ f(y(i − 1,t),u(i, p +1),x(i, r +1))=0.