0
$\begingroup$

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.

reg exp and NFA

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. I have added reg exp and NFA with 5 states for the language in the question. Please correct me if anything is wrong. $\endgroup$ – user3523469 Sep 8 '17 at 15:09
  • $\begingroup$ @user3523469 My comment were little confusing, so I have removed them. I will respond after checking your answer more carefully. $\endgroup$ – SSequence Sep 8 '17 at 15:58
  • $\begingroup$ @user3523469 Yeah your NFA seems about right to me. I think when you wrote $(000+001+011+100+101+110+111)$ there are just 7 of these (there have to be 8). You are missing $010$. Otherwise the regular expression also seems correct. $\endgroup$ – SSequence Sep 8 '17 at 19:25
0
$\begingroup$

You can refer to the following links https://www.tutorialspoint.com/automata_theory/dfa_minimization.htm

https://www.google.co.in/url?sa=t&source=web&rct=j&url=http://web.cs.ucdavis.edu/~rogaway/classes/120/winter12/min.pdf&ved=0ahUKEwjp6MHp9pTWAhVEM48KHdu3BxEQFghnMAw&usg=AFQjCNEMrxLBaLEEZD6aR9w28vUe_6w4kw

$\endgroup$
  • $\begingroup$ Thanks for the links. Very helpful. But can we work on finding out the language with out reducing the nodes? I have attached an image of large DFA in the question, but at first glance, I see the language is binary language {0,1} with out 1111 at the end. If I can somehow find the language of the DFA. I can directly work on NFA with less states (In this case reduce to 5 nodes) from the language. If this all fails, I will revert to the methods in the links provided. $\endgroup$ – user3523469 Sep 8 '17 at 6:29
  • $\begingroup$ I'll try to answer your query with adequate research I am not much of a dfa guu $\endgroup$ – Aflah Sep 8 '17 at 7:18

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.