3
$\begingroup$

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!

  • 0
    Pastafarianism!2012-05-31

1 Answers 1

3

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.

  • 0
    great, thanks! You saved my day! ;)2012-05-31