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

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.3. Input: Regular language L over I [ O ; Output: Largest FSM

language L FSM L .

1. Build a deterministic automaton A accepting L \ .IO/ ? .
2. Delete the initial state if it is a nonfinal state.
3. Delete all nonfinal states having incoming edges labeled with symbols from
alphabet O, together with their incoming edges.
4. 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

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 .

To obtain the largest subset of L that is the language of a complete FSM (IO-
progressive) we must apply one more pruning algorithm.
Procedure 3.1.4. Input: FSM Language L FSM over I [ O ; Output: Largest IO -

progressive FSM language Prog.L FSM / L FSM .
1. Build a deterministic automaton A accepting L FSM .
2. Iteratively delete all states that are final and for which 9 i 2 I with no outgoing
edge carrying the label i, together with their incoming edges, until the initial state
is deleted or no more state can be deleted. Delete the initial state if 9 i 2 I with

no outgoing edge carrying the label i.
3. If the initial state has been deleted, then Prog.L FSM / D; . Otherwise, let A
be the automaton produced by the procedure and Prog.L FSM / the language
that

A accepts. Any IO-progressive FSM language in L FSM

must be a subset of

Prog.L FSM /.
Theorem 3.6. Procedure 3.1.4 returns the largest IO -progressive subset of L FSM .

Proof. Similar to the proof of Theorem 3.3 . t

Proposition 3.7. An FSM whose language is L FSM or Prog.L FSM / can be
deduced trivially from A (obtained according to Procedure 3.1.4 ) by replacing pairs
of consecutive edges labeled, respectively, with i and o by a unique edge labeled i=o .

Proposition 3.8. Given a regular language L over alphabet I [ O ,let M be an
FSM over input alphabet I and output alphabet O . The language L r .M / of M is
contained in L iff L r .M / L FSM .
The proof is the same as the one of Prop. 3.5 .
Finally we characterize the Moore FSMs that are the reduction of a given FSM.
Notice that the language of a Moore FSM is a Moore language.