1
$\begingroup$

Describe a (general) procedure that, given some finite automaton M, produces a new finite automaton M’ with: M’ rejects ε, but accepts otherwise the identical language as M does.Note that M may or may not accept ε, while M’ does not!

My solution is to discuss the different cases. If M doesn't contain ε, then, don't need to produce a new M', but if M contains ε-transition, then convert it to DFA. I'm not sure my procedure is right or not.

Can someone come up with some more effective idea?

$\endgroup$
  • $\begingroup$ It's not clear what you do in the second (interesting) case. What if $M$ is already a DFA? Also, if you're not sure the procedure works, try it on something! $\endgroup$ – Yuval Filmus Jun 10 '13 at 3:00
  • 1
    $\begingroup$ Your approach is trivially wrong. Determinising does not change the language, so the resulting automaton still accepts the empty word. Think about how you decide algorithmically whether an automaton accepts the empty word. $\endgroup$ – Raphael Jun 10 '13 at 10:37
  • $\begingroup$ @Raphael: I guess, the OP implied to turn the initial state of the DFA into a non-excepting state. $\endgroup$ – frafl Jun 11 '13 at 19:40
4
$\begingroup$

Why go for a subtle or elegant answer? You can drive a screw in with a jackhammer, too.

  1. Define a DFA $M_{\epsilon}^{-1}$ for the language $\Sigma^* \setminus \{\epsilon\}$. Hint: it has two states for any $\Sigma$.
  2. Say how to construct $M'$ such that $L(M') = L(M) \cap L(M_{\epsilon}^{-1})$. Hint: use the Cartesian Product Machine construction.
$\endgroup$
  • 1
    $\begingroup$ If the coffeemaker already contains coffee powder, empty it, to get to a known state. $\endgroup$ – frafl Jun 11 '13 at 19:44
  • $\begingroup$ @frafl Sounds exactly like the usual approach in mathematics.</banter> $\endgroup$ – Raphael Jun 11 '13 at 19:54
  • 2
    $\begingroup$ Fun fact: if you determinise and minimise, you get the same automaton as with any other approach and worst-case runtime is not even different (assuming you want a minimal DFA). $\endgroup$ – Raphael Jun 11 '13 at 19:56
2
$\begingroup$

Hint: Duplicate the starting state.

$\endgroup$
  • $\begingroup$ you mean go back to start state? $\endgroup$ – user67584 Jun 10 '13 at 4:24
  • 1
    $\begingroup$ I mean what I wrote. $\endgroup$ – Yuval Filmus Jun 10 '13 at 13:53
  • $\begingroup$ Think about it. The empty word will only get accepted in the starting state (provided you don't have any $\epsilon$-transitions). What could you do then to make it not accepted? $\endgroup$ – jmite Jul 26 '13 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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