[Solved]: Finite automaton - language acceptance

Problem Detail: 

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"?

Asked By : Robert Hönig

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62748