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
    The diagrams look [a little bit](https://www.stanford.edu/group/aha/cgi-bin/wordpress/wp-content/uploads/2010/05/fsm.jpeg) like *the* [FSM](http://www.venganza.org/).2012-05-31
  • 0
    @Asaf: Aha! Thank you: you’ve just explained a popular culture reference that I ran into a while back.2012-05-31
  • 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
    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$?2012-05-31
  • 0
    @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$?2012-05-31
  • 0
    great, thanks! You saved my day! ;)2012-05-31