0
$\begingroup$

This question already has an answer here:

In this link it is mentioned:

A DFA is not powerful enough to recognize many context-free languages because a DFA can't count.

But counting is not enough -- consider a language of palindromes, containing strings of the form $ww^R$. Such a language requires more than an ability to count; it requires a stack.

I would extremely appreciate if someone could explain in simple words or refer a tutorial what is the meaning of not being able to count.

Moreover, DFA does not accept $\{0^n1^n \mid n \ge 1\}$ because it can't count or because it does not have stack?

Any help to clarify above points is truly appreciated.

$\endgroup$

marked as duplicate by Raphael Apr 21 at 12:15

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.

  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Apr 21 at 12:12
1
$\begingroup$

DFA has a finite memory. By finite memory, I mean, It can not store any information of infinite length. Let's take an example, $$ l = {0^n1^n | n > 0} $$ This is a very simple example of a language which can not be recognized by a DFA, because, to accept a word of the above language, the DFA need to count the number of 0's seen. The number of 0's can be infinite as n has no upper bound. Therefore this language is an irregular language. But if he we have an upper bound to n, then then any word of the language will be finite length and can be recognized by a DFA (just make those many number of states in the worst case).
Now, let's take another example: $$ l = { (01)^n | n > 0 } $$ The words of languge l can be of infinite length. But it does not imply that it is a irregular language, i.e. can not be recognized by any DFA, Because it has a pattern. DFA does not need to memorize the input symbol seen two states before the current state, hence, a finite memory can do the job.
In your example, $$ l = { WW^R} $$ DFA has to memorize the contents of W first, to recognize it's reverse, and there is no upper bound on the length of W. Hence it requires an infinite memory. This is very nice tutorial playlist on theory of computation by Prof. Harry Porter. The first 3 videos should clarify your doubts.

$\endgroup$

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