Equations Over Finite State Machines - The Unknown Component Problem: Theory and Applications - page 33

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.