3
$\begingroup$

In the book "The New Turing Omnibus", an excercise reads as the follows:

"Show that no finite automaton can accept the language consisting of all words of the form $a^n b^n, n=1,2,3,...$ The formula represents $n$ a's followed by $n$ b's."

I have no idea why a finite automaton shouldn't accept such words. Couldn't one simply design an automaton that reads a word and always outputs "Accepted"?

$\endgroup$
  • $\begingroup$ did you notice that both $a$ and $b$ have the same suffix $n$? That language is made of the words $ab$, $aabb$, $aaabbb$, etc. but does not include $abb$ or $aab$ for example. Basically the automaton has to read the $a$s and *count* what is the $n$, and after that check that there are exactly $n$ $b$s, but since the string can be arbitrarily large how can you count without an upperbound on the size with only finite states? $\endgroup$ – Bakuriu Aug 20 '16 at 18:41
  • $\begingroup$ If this is not a misunderstanding of the definition of language acceptance, it's a duplicate of our reference question. $\endgroup$ – Raphael Aug 23 '16 at 8:49
9
$\begingroup$

Check the definitions. The language accepted by an automaton is the set of strings it accepts. So, for an automaton to accept a particular language (e.g., $\{a^nb^n\mid n\geq 1\}$), it must not only accept every string in the language, but also reject every string not in the language. Your suggestion of the automaton that just accepts every input meets the first criterion but not the second.

$\endgroup$
4
$\begingroup$

In formal language theory, when we say an automaton accepts a language, we mean that it accepts exactly that language, no more, no less.

Your automaton accepts words in $a^n b^n$, but also words with different numbers of as and bs. No finite automaton is capable of distinguishing words with equal numbers of as and bs, and words with different numbers.

You will want to read up on the pumping lemma in order to prove this.

$\endgroup$
  • 2
    $\begingroup$ Well, you have to prove it. $\endgroup$ – Yuval Filmus Aug 20 '16 at 19:19
  • 1
    $\begingroup$ @piepi The intuition is that you need to count how many as and bs are in the word, and since the number can get arbitrarily large, you can't store it in finite memory. There's a largest number that you can represent in the state space of any finite machine. $\endgroup$ – jmite Aug 20 '16 at 21:35
  • 1
    $\begingroup$ @piepi Try to design one that can. $\endgroup$ – immibis Aug 21 '16 at 2:10
  • 1
    $\begingroup$ @piepi You can design a finite automaton which recognizes $a^2b^2$, you cannot design one recognizing $a^nb^n$ for all integers $n$. $\endgroup$ – doganulus Aug 21 '16 at 16:57
  • 1
    $\begingroup$ @piepi See our reference question. $\endgroup$ – Raphael Aug 23 '16 at 8:49
2
$\begingroup$

Let $\cal A$ be a deterministic finite automaton that accepts the language $L = \{a^n b^n : n \geq 0\}$. Denote by $q_n$ the state that $\cal A$ arrives at after reading the word $a^n$. Since $\cal A$ has only finitely many states, by the pigeonhole principle we must have $q_n = q_m$ for some $n \neq m$.

What happens when $\cal A$ reads $b^n$, starting at $q_n$? On the one hand, since $a^n b^n \in L$, $\cal A$ must arrive at an accepting state. On the other hand, since $a^m b^n \notin L$ and $q_m = q_n$, $\cal A$ must arrive at a rejecting state. This contradiction shows that $\cal A$ cannot exist.

This argument can be generalized to give a neat algebraic characterization of the regular languages, known as Myhill–Nerode theory. Given a language $L$, say that two words $x,y$ are equivalent if for all words $z$, either $xz,yz \in L$ or $xz,yz \notin L$. If $x,y$ are not equivalent that any automaton accepting $L$ must reach different states after reading $x$ and $y$. Hence if there are infinitely many pairwise inequivalent words, $L$ is not regular. The Myhill–Nerode theorem states that the converse also holds: if any collection of pairwise inequivalent words is finite, then $L$ is regular.

Normally this is stated in terms of equivalence classes: $L$ is regular if and only if the Myhill–Nerode relation (the equivalence relation defined in the preceding paragraph) has finitely many equivalence classes. Moreover, if $L$ is regular and the Myhill–Nerode relation has $n$ equivalence classes, then every DFA accepting $L$ must have at least $n$ states, and there is a unique DFA with exactly $n$ states, known as the minimal DFA.

$\endgroup$
2
$\begingroup$

A finite automaton does not has a memory unit associated with it. It only knows its current state and behaves according to the input provided to the current state.It cannot remember how many 'a's it has already read and how many 'b's it has to further count so as to make number of 'a's equal to number of 'b's ( as 'n' is a variable entity). But if we provide specific number of 'a's and 'b's ( like a3b3 or a5b5) then the automaton will have a dedicated state for every alphabet read.

Another ways of getting it

A finite automaton is a machine to accept regular languages. We can prove by pumping lemma that anbn is not a regular language.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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