A finite automaton can be interpreted as a language recognizer by one of the methods discussed in section 2. That is, it defines a function from to . The language accepted consists of those sentences on which computes true ().
This meaning of an automaton is given by providing a meaning function mapping an automaton in Automata to a formal language, i.e. to a map from into propositions . We give this meaning by composing 3 simpler functions:
(We can also write this as
a sentence is said to be accepted by if for some in . The set of all accepted by is denoted . That is, .
This is a very elegant definition, it can be even more compactly written without reference to in , namely
So our definition of the computation of state of automaton on string (thought of as is
Recall that is the initial state.
Notice that with this definition the automaton starts processing with the ``tail-most'' symbol working toward the head. The input is extended at the head by ``consing on'' more symbols.
The usual convention in programming (Lisp, Scheme, ML, Java) is to display lists with the head on the left, as or . This means that the automaton is thought of as processing from right to left with input being extended on the left.
Unfortunately, Hopcroft and Ullman chose to display lists with the head on the right, as or , so their automata ``move'' from left to right and input is extended on the right. Thus, when they speak of ``right invariant'' behavior, we speak of ``left invariant'' behavior.
To keep the terminology abstract and independent of display, we use the term extension invariance. We define an operation extend in which string is added to string . This extension is added at the head, so we write extend for the append operation. Hopcroft and Ullman use .