Hardware Reference
In-Depth Information
3.1.2
Languages of FSMs
We now introduce the notion of a language associated to an FSM. This is achieved
by looking to the automaton underlying a given FSM. For our purposes, we
define two related languages: one over the alphabet I
O and the other over the
alphabet I
[
O, naturally associated, respectively, with synchronous and parallel
composition, as it will be seen later.
For a language over I
O, the automaton coincides with the original FSM where
all states are made accepting and the edges carry a label of the type .i; o/.
For a language over I
[
O, the automaton is obtained from the original FSM, by
replacing each edge .i;s;s
0
;o/ by the pair of edges .i;s;.s;i// and .o;.s;i/;s
0
/
where .s; i / is a new node (non-accepting state). All original states are made
accepting. The automaton is deterministic because from .i;s;s
1
;o
1
/ and .i;s;s
2
;o
2
/
the edges .i;s;.s;i//, .o
1
;.s;i/;s
1
/ and .o
2
;.s;i/;s
2
/ are obtained (the same edge
.i;s;.s;i//works in both cases).
Definition 3.1.7.
Given an FSM M
Dh
S; I; O; T; r
i
, consider the finite automa-
ton F.M/
Dh
S; I
O; ; r; S
i
,where..i; o/; s; s
0
/
2
iff .i;s;s
0
;o/
2
T .The
language accepted by F.M/is denoted L
r
.M /, and by definition is the
-language
of M at state r . Similarly L
s
.M / denotes the language accepted by F.M/ when
started at state s, and by definition is the
-language of M at state s.
Definition 3.1.8.
Given an FSM M
Dh
S; I; O; T; r
i
, consider the finite automa-
ton F.M/
Dh
S
[
.S
I/;I
[
O; ; r; S
i
,where.i;s;.s;i//
2
^
.o;.s;i/;s
0
/
2
iff .i;s;s
0
;o/
2
T . The language accepted by F.M/ is denoted L
r
.M /, and by
definition is the
[
-language
of M at state r . Similarly L
s
.M / denotes the language
accepted by F.M/ when started at state s, and by definition is the
[
-language
of M at state s. By construction, L
s
.M /
.
IO
/
?
,where
IO
denotes the set
f
io
j
i
2
I; o
2
O
g
.
In both cases,
2
L
r
.M / because the initial state is accepting. An FSM M is
trivial
iff L
r
.M /
Df
g
.
Definition 3.1.9.
A language L is an
FSM language
if there is an FSM M such
that the associated automaton F.M/accepts L. The language associated to a DFSM
is sometimes called a
behavior
.
2
Remark.
When convenient, we will say that FSM M has property X if its associated
FSM language has property X .
Definition 3.1.10.
State t of FSM M
B
is said to be a
reduction
of state s of FSM
M
A
(M
A
and M
B
are assumed to have the same input/output set), written t
s,
2
The language associated to a NDFSM includes a set of behaviors.
Search WWH ::
Custom Search