# Finding the mistake in a new way of generating FSMs from regular expressions

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$:

1. There is exact one final state
2. 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)$)
3. 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.

-
The diagrams look a little bit like the FSM. –  Asaf Karagila May 31 '12 at 10:13
@Asaf: Aha! Thank you: you’ve just explained a popular culture reference that I ran into a while back. –  Brian M. Scott May 31 '12 at 10:46
Pastafarianism! –  David Lewis May 31 '12 at 12:11

Suppose that I’ve a one-state machine $E_a$ that recognizes $a^*$ and another, $E_b$, that recognizes $b^*$; combining them in the second way would result in a one-state machine that recognized $(a\lor b)^*$, not $a^*\lor b^*$. This violates both (2) and (3), but you can use similar ideas to show that violating either of them individually can produce undesired results.
thank you, that helped me a lot. Nevertheless how do I create an FSM that violates only (3)? If I'm not allowed to go back to the initial state how can I affect $E_b$ from $E_a$? –  muffel May 31 '12 at 10:23
@muffel: Suppose that $E_e$ is a three-state machine for $ab^+$, where the acceptor state loops on $b$, and $E_f$ is a three-state machine for $ba^+$ of the same design. If you combine them in the second way, what language does the resulting machine recognize? You even have problems if only one of them loops: what happens if $E_f$ accepts $ba$? –  Brian M. Scott May 31 '12 at 10:28