I am practicing problems around NFA and DFA.
I have seen many questions on how to convert NFA to DFA and DFA to Regular expression etc.
But I have seen very different question and I am stuck on how to proceed with the following question?
Given DFA. Convert this DFA to NFA with 5 states.
DFA IMAGE ATTACHED
I plan is to find a language and regular expression first and then try to convert regular expression to NFA with 5 states. But I had hard time just to find the language it accepts.
How to approach these problems. And to how to find language or regular expressions for large DFA's? Are there any algorithms or rules?
Edit:
Regular exp for the language and NFA with 5 states are added in the diagram.
Best Answer
I believe at least the intention of question seems to understand the language of the DFA and then use that to build the NFA.
I think I understand the language of DFA. Hopefully you can use that description to find a corresponding NFA. It seems to me that it shouldn't be too difficult, but if you have trouble with corresponding NFA you can mention it in comments.
First of all we can observe that the DFA rejects all strings with length less than or equal to 3. Now suppose we have a string of length 4 or more as input. Denote the input string by x. First we note that the alphabet set is $\Sigma=\{0,1\}$. Then the input string can always be written as: $$x=s.abcd$$ Here $s$ is some arbitrary string (that can also be empty) and $a,b,c,d \in \Sigma$. Now the given DFA accepts a string of length four or more if and only if the alphabet corresponding to $a$ is $0$.
In short description, the DFA checks the fourth-last alphabet of any input string $x$. If the fourth-last alphabet is equal to $0$ it accepts it and otherwise rejects it.
Note that we can understand it better why it is so, if we mark the states a little different. For example, look at the state marked [001] for example. It can really be marked as [1001]. The state [01] can be marked as [1101]. Similarly state [0] can be marked as [1110]. The start state of DFA can be marked as [1111]. State [011] can be marked as [1011] and so on...
These states essentially store the information about the last four alphabet of the input string.