Hardware Reference
In-Depth Information
Chapter 3
Equations Over Finite State Machines
3.1
Finite State Machines and Their Languages
3.1.1
Finite State Machines
Definition 3.1.1.
A
finite state machine
(FSM) is a 5-tuple M
Dh
S; I; O; T; r
i
where S represents the finite state space, I represents the finite input space,
O represents the finite output space and T
I
S
S
O is the transition
relation. On input i , the FSM at present state p may transit to next state n and
produce output o iff .i;p;n;o/
2
T . State r
2
S represents the initial or reset
state. We denote the projection of relation T to I
S
S (next state relation) by
S , i.e., .i;s;s
0
/
,9
o.i;s;s
0
;o/
2
T
n
I
S
2
T
n
T ; similarly, we denote
the projection of relation T to I
S
O (output relation) by T
o
I
S
O,
,9
s
0
.i;s;s
0
;o/
2
T . Sometimes ı is used instead of T
n
and
i.e., .i;s;o/
2
T
o
instead of T
o
.
If at least one transition is specified for each present state and input pair, the FSM
is said to be
complete
. If no transition is specified for at least one present state and
input pair, the FSM is said to be
partial
.
An FSM is said to be
trivial
when T
D;
, denoted by M
.
The notion of a partial FSM should not be confused with that of an incompletely
specified FSM (ISFSM), which is traditionally employed in the digital design
literature to denote a form of restricted non-determinism widely used in the
specification of sequential logic designs (see [66]). ISFSMs are introduced in
Definition
3.1.4
.
It is convenient to think of the relations T
n
and T
o
as functions T
n
W
I
!
2
S
S
and T
o
W
I
S
!
2
O
.
Definition 3.1.2.
An FSM M
0
Dh
S
0
;I
0
;O
0
;T
0
;r
0
i
is a
submachine
of FSM
Dh
S; I; O; T; r
i
if S
0
S , I
0
I , O
0
O, r
0
D
r ,andT
0
is a restriction of
M
T to the domain of definition I
0
S
0
S
0
O
0
.
Search WWH ::
Custom Search