Next: Equivalence Relations and
Up: Finite Automata
Previous: Definition
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:
- A function from an automaton and an input string to a state. This is called
- Associating with the resulting state of compute_list_ml a boolean value using the final state component, a function
States 
- Associating with the automaton the propositional function
saying that the final state is tt. Let
be the final state
function.
(We can also write this as 
Hopcroft and Ullman follow the same approach but they use only the
first function and leave the other two implicit since they are so
simple. They define the first function as
for 
a string and 
a character of the alphabet. They say:
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 
.
Next: Equivalence Relations and
Up: Finite Automata
Previous: Definition