0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Somehow both. The input can be any string over the input alphabet, however the automat ends in an accepting state only if that string belongs to the accepted language. $\endgroup$ – Hagen von Eitzen Sep 27 '15 at 22:55
  • $\begingroup$ Where did you see "input language"? $\endgroup$ – J.-E. Pin Sep 27 '15 at 23:23
  • $\begingroup$ @J.-E.Pin in my lecture notes, so maybe it's a mistake $\endgroup$ – Celeritas Sep 27 '15 at 23:35
0
$\begingroup$

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.

$\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.