Equations Over Languages and Finite Automata - The Unknown Component Problem: Theory and Applications - page 30

The automaton is complete and deterministic.
4 inputs 8 states 23 transitions
Inputs = { i1(3), i2(3), v1, v2 }

- 2 0 -
(0,1) (1,2) 0 -
0 - 0 -

s0

(1,2) 0 1 -
2 (0,1) 1 -

- - 1 1 - - 1 0 s2 - (1,2) 1 0

- (1,2) 0 0 - (1,2) - 1 - 0 0 0 - (1,2) 1 1

- 2 1 -
(0,1) (1,2) 1 -
0 - 1 -
(1,2) 0 0 -
2 (0,1) 0 -

s4 s5 - 0 0 0 - 0 - 1

s6 - - 1 0 - 0 - 1

- (1,2) - 1
- (1,2) 0 -
- 0 1 0

- - - 1
- - 0 -

- - 0 1 - - - 0 - 0 0 1

s7

- (1,2) 0 1
- 0 1 1

- - - 0

- - - - - - - -

DC1 DC

Fig. 2.12 Graphical output of BALM showing the automaton traffic-xfsm min.aut de-
scribing the largest solution automaton of the traffic light controller problem

2.4. Somebody claims that there is a more efficient way to solve the lan guage equa-
tion F X S . Instead of computing the solution .F \ S " U V / # U V , compute as
a solution .F \ S " U V / # U V . The advantage would be to avoid a determinization
because the second complementation is performed before the projection (the latter
introduces non-determinism and so the need for determinization). Is it correct? Are
the two expressions equivalent ? Is one contained in the other?