patternMinor
Finite automaton - language acceptance
Viewed 0 times
acceptancefiniteautomatonlanguage
Problem
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"?
"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"?
Solution
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.
Context
StackExchange Computer Science Q#62748, answer score: 9
Revisions (0)
No revisions yet.