# Finding nfa or dfa for a language [duplicate]

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

• 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?
– Evil
Jun 3, 2016 at 16:46
• Probably a trick exercise. Did you already read about the pumping lemma? Then try to apply it to show that $L$ is not regular. Jun 3, 2016 at 19:05

## 2 Answers

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.

• 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. Jun 3, 2016 at 17:29
• @DavidRicherby Yes, but it does give something OP can look into or further inquire about Jun 3, 2016 at 17:35
• @AMomchilov sounds like you are thinking of some other definition of index. Just read this: engineering.dartmouth.edu/~d25559k/ENGS122_files/Lectures_Notes/… Jun 3, 2016 at 17:42
• 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.
– Raphael
Jun 3, 2016 at 22:50
• Thanks for your contribution guys, I clearly have a lot more to study Jun 8, 2016 at 10:24