As described e.g. here (see pp. 2-3) a final state machine can be easily constructed from a regular expression. For the union of to expressions $e + f$ I need to look at the original way of construction and an alternative one (sorry for the graphics, I'm not an artist at all):
The new way of building the union merges the initial and final states of both subexpressions. It works properly if three invariants are respected for each of the two subexpressions $e$ and $f$:
- There is exact one final state
- There is no transition into the initial state ($\forall q \in Q.\forall a \in \Sigma \cup \{\lambda\} : q_0 \not\in \delta(q,a)$)
- There is not transition out of the final state ($\forall a \in \Sigma \cup \{\lambda\} : \delta(q_f,a) = \emptyset$)
What I need to show is: A FSM constructed using the "new" way does not recognize $L(E_e) \cup L(E_f)$ if (only)
- i) the second invariant is not followed
- ii) the third invariant is not followed
I tried to build a lot of FSM's, but I don't get why merging the initial and final states may lead to a FSM that doesn't recognizes a language if there are transitions into the inital or out of the final state.
Could you please help me to find FSMs for i) and ii)?
Thanks in advance!