Hardware Reference
In-Depth Information
intersection A " I 2 O 2 \ C " U V does not include the empty string, neither does its
projection .A " I 2 O 2 \ C " U V / # I 2 U V O 2 ,thatisA C . Therefore A C includes
the empty string, i.e., 2 S
¤; .
t
Example 3.16. Consider the FSMs M A Dh S A ;I 1 V; U O 1 ;T A ;sa i and M C D
h S C ;U;V;T C ;s1 i with S A Df sa g , T A Df .01; sa; sa; 01/, .00; sa; sa; 01/,
.11; sa; sa; 10/, .10; sa; sa; 10/ g , S C Df s1 g , T C Df .1;s1;s1;1/,
.0;s1;s1;0/ g . The equation M A M X M C yields the language equation
A X C with solution S Df g , i.e., the corresponding FSM solution M X
produces only the empty word. The reason is that the i=o combinations of M C ,i.e.,
1=1; 0=0 do not match any i=o combination of M A , i.e., 0=1; 1=0.
In general S is not an FSM language. To compute the largest FSM language
contained in S ,thatisS FSM , we must compute the largest prefix-closed language
contained in S .
Theorem 3.17. Let A and C be FSM languages. The largest FSM l anguag e that is
a solution of the equation A X
C is given by S FSM ,where S
D A C . S FSM
is
obtained by applying Procedure 3.1.1 to S . S FSM
contains at least the string .
If A S FSM
D C then S FSM is the largest solution of the FSM language equation
A X
D C .
Thus, the synchronous FSM language equation A X C is always solvable, since
the solution includes at least the empty string and so its prefix-closure does too. In
other words, the trivial FSM is always a solution of the synchronous FSM equation
A X C .
Example 3.18. Consider the equation M A M X M C , with M A and M C shown,
respectively, in Fig. 3.4 a,c. The FSMs are composed with respect to the rectification
topology and their alphabets are I 1 Df i 1 ;i 2 g , O 1 Df o 1 ;o 2 g , U Df u 1 ; u 2 g and
V Df v 1 ; v 2 g . M A is a partial FSM, e.g., the transitions from state a under inputs i 1 v 2
and i 2 v 2 are missing. The automata of the related languages are shown, respectively,
in Fig. 3.4 b,d. The intermediate steps to compute the solution are demonstrated
in Fig. 3.4 e-g. The automaton generating the largest language solution, S D
.A \ .C " U [ V / # U [ V , is portrayed in Fig. 3.4 h. The state labeled dc accepts strings
that are not in the language of the context. Notice that S is not prefix-closed, since
string u 1 v 1 u 2 v 1 2 S ,but u 1 v 1 62 S ; its largest prefix-closed sublanguage yields the
largest FSM solution M X showninFig. 3.4 i. M X is a PNDFSM and the composition
of any DFSM reduction of M X with M A produces the trivial machine.
Example 3.19. Consider the following variants of the context FSM M A in the
equation M A M X M C , studied in Example 3.18 . The specification FSM
M C is the same. The variants of M A are M A , M A and M A , shown respectively
in Fig. 3.5 a,d,f. They are all complete FSMs, whereas M A of Example 3.18 is a
partial FSM. The solution of M A M X M C is M X in Fig. 3.5 c. M X is a partial
FSM and M A M X D M , i.e., the composition yields the trivial FSM that is the
“ultimate” partial machine, because each external input sequence causes a violation
 
Search WWH ::




Custom Search