-1
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by Raphael Jun 3 '16 at 22:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 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 '16 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 '16 at 19:05
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 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$ – David Richerby Jun 3 '16 at 17:29
  • $\begingroup$ @DavidRicherby Yes, but it does give something OP can look into or further inquire about $\endgroup$ – Alexander Jun 3 '16 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 '16 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 '16 at 22:50
  • $\begingroup$ Thanks for your contribution guys, I clearly have a lot more to study $\endgroup$ – Martins Jr. Divine Okoi Jun 8 '16 at 10:24

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