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

Fig. 2.4 Communication system described in Sect. 2.3.2

( Deliver ) represent the interfaces of the communication system with the environ-
ment (the users). The converter X translates the messages delivered by the sender
PS (using the alternating bit protocol) into a format that the receiver PR understands
(using the non-sequenced protocol). For example, acknowledgement messages A
delivered to the converter by the receiver are transformed into acknowledgements of
the alternating bit protocol ( a0xc to acknowledge a 0 bit and a1xc to acknowledge a
1 bit) and passed to the sender by the channel ( a0cs to acknowledge a 0 bit and a1cs
to acknowledge a 1 bit); data messages are passed from the sender to the channel
( d0sc for a message controlled by a 0 bit and d1sc for a message controlled by a
1 bit) and then from the channel to the converter ( d0cx for a message controlled
by a 0 bit and d1cx for a message controlled by a 1 bit) to be transformed by the
converter into a data message D for the receiver.
We model the components as I/O automata [89], which recognize prefix-closed
regular languages, and we solve their language equations. Figure 2.5 shows the
automata of the components of the communication system. Missing transitions go
to a trap (non-accepting) state, that loops to itself under any event.
Figure 2.6 shows the largest prefix-closed solution S D PS ˘ PC ˘ PR ˘ SS of
the converter problem. All missing transitions go to an accepting trap state dc (not
shown), that would loop to itself under any event; e.g., the initial state would have
a transition to state dc under events A; a0xc; a1xc; d1cx. These transitions are not
indicated in the state transition graph of the automaton of the solution language to
avoid cluttering the picture. State dc can be termed the don't care state, because it is
introd uce d during the determinization step to complete the automaton PS ˘ PC ˘
PR ˘ SS, before the final complementation. It is reached by transitions that cannot
occur due to impossible combinations of events in the composition of PS ˘ PC ˘ PR
and S , and so it does not matter how S behaves, once it is in state dc (thus the
qualification don't care state). This makes the largest solution S non-deterministic.
The solution presented in [78] and [56] does not feature this trap accepting state and
so it is not complete (in [78] and [56] all missing transitions of the solution are
supposed to end up in a non-accepting trap state, a fail state); without the above dc
state, one gets only a subset of all solutions (in particular the complete solutions are
missed) and this might lead to an inferior implementation.