Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

enter image description here

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.

Could you please help me to find FSMs for i) and ii)?

Thanks in advance!

share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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
great, thanks! You saved my day! ;) – muffel May 31 '12 at 10:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.