Next: Equivalence Relations and Up: Finite Automata Previous: Definition

## Semantics of Automata

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:

1. A function from an automaton and an input string to a state. This is called
2. Associating with the resulting state of compute_list_ml a boolean value using the final state component, a function States
3. 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

karla@cs.cornell.edu
Wed Jul 2 08:55:38 EDT 1997