HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Finite automaton - language acceptance

Submitted by: @import:stackexchange-cs··
0
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"?

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.