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

iff L t .M B / L s .M A /. States t and s are equivalent states , written t Š s,ifft s
and s t , i.e., when L t .M B / D L s .M A /. An FSM with no two equivalent states is
a reduced FSM.
Similarly, M B is a reduction of M A , M B M A ,iffr M B , the initial state of M B ,
is a reduction of r M A , the initial state of M A .WhenM B

M A and M A M B then

M A and M B are equivalent FSMs , i.e., M A Š M B .
For complete DFSMs reduction and equivalence of states coincide. An FSM can
be reduced by merging the equivalent states with the classical state minimization
procedure [63]. Given an FSM language, there is a family of equivalent FSMs
associated with it; for simplicity we will usually speak of the FSM associated with
a given FSM language. In this paper, complete deterministic FSMs are assumed to
be reduced, unless stated otherwise.
An FSM language is regular, whereas the converse is not true.

Theorem 3.1. A regular language over alphabet I O is the language of a
complete FSM over input alphabet I and output alphabet O iff L is prefix-closed
and I -progressive. A regular language that is prefix-closed, but not I -progressive,
is the language of a partial FSM.

Notice that the merging of the notions of complete FSM and I -progressive
associated language is due to the fact that FSMs are assumed to be PNDFSMs,
i.e., their underlying automaton is deterministic, therefore a word has a unique run
(sequence of transitions), from which an extension is possible under any input.

Theorem 3.2. A regular language over alphabet I [ O is the language of a
complete FSM over input alphabet I and output alphabet O iff L

. IO / ? , L is

. IO / ?

IO-prefix-closed and IO-progressive. A regular language L that is IO-

prefix-closed, but not IO-progressive, is the language of a partial FSM.

Given a regular language L over alphabet I O, an algorithm follows to build
L FSM , the largest subset of L that is the -language of an FSM over input alphabet
I and output alphabet O.

Procedure 3.1.1. Input: Regular language L over I O ; Output: Largest FSM

language L FSM L .

1. Build a deterministic automaton A accepting L.
2. Delete all nonfinal states together with their incoming edges.
3. If the initial state has been deleted, then L FSM

A be the

D; . Otherwise, let

A accepts. If

automaton produced by the procedure and L FSM

the language that

A,then A accepts the trivial

there is no outgoing edge from the initial state of

FSM language L FSM Df g , otherwise it accepts a nontrivial FSM language

L FSM . Any FSM language in L must be a subset of L FSM .

In general this procedure leads to a partial FSM. To obtain the largest subset of L
that is the language of a complete FSM we must apply one more pruning algorithm.