I'm trying to study for the summer ahead of class I saw this question, please how do I go about it?
Find NFA/DFA for the language $L = \{0^n1^n : n \in N\}$
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ What exactly is your question? What have you tried? What have you read? Where did you get stuck? Are you sure that DFA/NFA will be able to solve this? $\endgroup$– EvilJun 3, 2016 at 16:46
-
2$\begingroup$ Probably a trick exercise. Did you already read about the pumping lemma? Then try to apply it to show that $L$ is not regular. $\endgroup$– BakuriuJun 3, 2016 at 19:05
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
That language is not regular, thus no finite automaton, be it a DFA, NFA or εNFA, is sufficiently powerful to express it.
To express this language, you'll need a context-free grammar, a push down automaton, or a Turing machine.
$\begingroup$
$\endgroup$
5
This language has infinite index, thus needs an infinite number of states according to the Myhill–Nerode theorem. You can't have a finite state automaton for it.
-
3$\begingroup$ This answer is correct, but somebody who can't instantly recognize that $\{0^n1^n\mid n\in\mathbb{N}\}$ is non-regular probably doesn't know enough to use Myhill-Nerode. $\endgroup$ Jun 3, 2016 at 17:29
-
$\begingroup$ @DavidRicherby Yes, but it does give something OP can look into or further inquire about $\endgroup$ Jun 3, 2016 at 17:35
-
1$\begingroup$ @AMomchilov sounds like you are thinking of some other definition of index. Just read this: engineering.dartmouth.edu/~d25559k/ENGS122_files/Lectures_Notes/… $\endgroup$– PavelJun 3, 2016 at 17:42
-
1$\begingroup$ I note that you are trying to help people -- that's great, thanks! However, you may want to be aware of our reference questions that cover many standard problems; there is often no need to give the same answer an upteenth time. $\endgroup$– RaphaelJun 3, 2016 at 22:50
-
$\begingroup$ Thanks for your contribution guys, I clearly have a lot more to study $\endgroup$ Jun 8, 2016 at 10:24