0
$\begingroup$

I am learning about state machines from the Stanford online cs143 course. Here I have tried to build a nondeterministic finite automaton for the regular expression (1+0)*1, but when I attempt to convert it to a DFA I find that the epsilon closure of the initial state A ends up having two outputs for the value 1, which I imagine would be impossible for a deterministic automaton.

I understand that my NFA differs from the instructors, but I'm unsure of whether or not it is valid. If it is valid, why am I having difficulty converting it to a DFA?

diagram of nfa for (1+0)*1

$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Mar 28 '16 at 13:13
  • 1
    $\begingroup$ Note that you can verify equivalence of NFAs by 1) converting to DFA and 2) minimizing; both are mechanical tasks. $\endgroup$ – Raphael Mar 28 '16 at 13:14
  • $\begingroup$ I'm sorry if it seems like I'm trying turn you all into my personal homework checkers. I had a legitimate question that is actually very general to NFA: What happens when e-clos(X) contains duplicate elements? Admittedly, the title of the question makes it seem like I'm just being lazy with some homework. $\endgroup$ – Miles Apr 6 '16 at 7:37
2
$\begingroup$

Yes, your NFA is correct. You are probably making some mistake during your conversion to a DFA.

Note that after the conversion from the NFA to the DFA, the states will no longer be $S = \{A,B,C,D,E\}$. Instead they will be all possible subsets of $S$. So in your case $A$ is not giving two different transitions to $C$ and $E$, instead it is giving one single transition to the state $\{C,E\}$

$\endgroup$

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.