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\}$

  • 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$
    – Evil
    Jun 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$
    – Bakuriu
    Jun 3, 2016 at 19:05

2 Answers 2


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.


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$
    – Alexander
    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$
    – Pavel
    Jun 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$
    – Raphael
    Jun 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.