0
$\begingroup$

So as the title says i m trying to find this NFA. So far i thought to make an NFA that "guesses" what comes after the first 0 and i got this: enter image description here

After some time trying to get rid of all the extra (7 !) states i put in i got to this beauty: enter image description here

But now i cant figure out how to get rid of the one extra state. Also if you have any tips on how to go to simpler NFA's instead of what i did (like a thought process for this problem) i would appreciate it a lot. Thank you

$\endgroup$
1
$\begingroup$

Simply remove state 2, and make a transition from 1 to 5 directly. This will get rid both of a state (state 2) and a connection (the epsilon connection)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, it was really simple indeed but i didn't see it somehow. $\endgroup$ – megan May 30 at 11:28
1
$\begingroup$

From the theoretical perspective: there is a completely algorithmic procedure that given a DFA returns an equivalent DFA with the minimum number of states.

In your specific case: remove the $\epsilon$ transition and merge state $2$ with state $5$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ i know of the DFA algorithm, but we arent taught the NFA one. Thanks for your help $\endgroup$ – megan May 30 at 11:31
  • 1
    $\begingroup$ There is also an algorithmic construction to convert any NFA into a DFA. Apply this first, then minimize the resulting DFA. $\endgroup$ – Steven May 30 at 11:34
  • $\begingroup$ Although in this specific example, its required to find a minimal NFA, and converting it into a DFA will just increase it's size overall (even if you try to minimize it later) $\endgroup$ – nir shahar May 30 at 11:38
  • $\begingroup$ There is no known efficient algorithm to convert a DFA to an equivalent minimal NFA. In fact this problem is PSPACE-hard. An algorithm in PSPACE is the following: minimize your DFA and let $n$ be the number of states of the resulting DFA. Consider all the (at most $(|\Sigma|+1)^{(n-1)(n-2)} \cdot 2(n-1)^2$) NFAs with up to $n-1$ states (guess the transitions, the number of final states and whether the initial state is final). Check if the language accepted by any of them matches the language of your DFA (this is in P). $\endgroup$ – Steven May 30 at 12:32

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.