Hardware Reference
In-Depth Information
Definition 3.1.3.
A
deterministic FSM
(DFSM) is an FSM where for each pair
.i; p/
2
I
S , there is at most one next state n and one output o such that
.i;p;n;o/
2
T , i.e., there is at most one transition from p under i . An FSM that is
not a DFSM is a
non-deterministic finite state machine
(NDFSM).
In a DFSM the next state n and the output o can be given, respectively, by a next
state function n
D
T
n
.i; p/ and an output function o
D
T
o
.i; p/,whereT
n
and T
o
may be partial functions when the DFSM is partial.
Definition 3.1.4.
An
incompletely specified FSM
(ISFSM) is a NDFSM such that,
for a given input and present state, either there is a unique next state and output, or
the next state is a designated don't care state DN C and any output is produced;
moreover, at the state DN C under any input there is a self-loop and any output is
produced.
Definition 3.1.5.
An NDFSM is a
pseudo non-deterministic FSM
(PNDFSM)
[142], or
observably non-deterministic FSM
[28], or
observable FSM
[130], if for
each triple .i;p;o/
2
I
S
O, there is at most one state n such that .i;p;n;o/
2
T .
The qualification “non-deterministic” is because for a given input and present state,
there may be more than one possible output; however, edges (i.e., transitions)
carrying different outputs must go to different next states. The further qualification
“pseudo” non-deterministic is because its underlying finite automaton is determin-
istic. In a PNDFSM the next state n, if it exists, is unique for a given combination of
input, present state and output, so it can be defined by a partial next state function
n
D
T
n
.i;p;o/. The output is represented by a relation T
o
I
S
O, because
the output is non-deterministic in general.
Definition 3.1.6.
A complete FSM is said to be of
Moore
type if .i;p;n;o/
2
T
implies that for all i
0
there is n
0
such that .i
0
;p;n
0
;o/
2
T .
1
The transition relation T of an FSM can be extended in the usual way to a relation
on I
?
O
?
: given a present state p and an input sequence i
1
:::i
k
S
S
2
I
?
, .i
1
:::i
k
;p;n;o
1
:::o
k
/
2
T iff there is a sequence s
1
:::s
k
C
1
such that s
1
D
p;:::;s
k
C
1
D
n and for each j
D
1;:::;k it holds that .i
j
;s
j
;s
j
C
1
;o
j
/
2
T .
A similar extension can be defined for T
p
and T
n
.
Here FSMs are assumed to be pseudo non-deterministic, unless otherwise stated.
It is always possible to convert a general NDFSM into a PNDFSM by subset
construction.
1
Notice that this definition allows for NDFSMs of Moore type, contrary to the more common
definition of Moore type: for each present state p there is an output o such that all transitions
whose present state is p carry the same output o.
Search WWH ::
Custom Search