Does finite automata take an alphabet or language as input?

428 Views Asked by At

I know this is a bit pedantic but I'm curious of the definition of finite automata. In Theory of Computation Sipser states

The formal definition says that a finite automaton is a list of those five objects: set of states, input alphabet, rules for moving, start state, and accept states.

I've seen definitions where "input alphabet" is replaced by "input language". Which is right? Isn't it more right to say "language" as a machine recognizes the strings that make up the language, not the individual symbols that make up the alphabet?

1

There are 1 best solutions below

0
On BEST ANSWER

An automaton takes neither an alphabet or a language as input, it takes a string as input. Whether you think of this string coming from an input language or an input alphabet is not really important from a theoretical standpoint. If we are working with an input alphabet $\Sigma$, then the input language is understood to be $\Sigma^*$. And if you are working with an input language, then the input alphabet would be understood to be the symbols used in the language.

From a practical point of view, however, if we want to implement an automaton on a computer, the alphabet representation is the only viable one, since it is finite (or at least, can be finite), whereas the language generated from the alphabet is necessarily infinite. It is true that you could specify a finite language of input strings, but I'm not really sure what you would gain from this.