1.1.2 Finite State Automata

Finite State Automata.

In the previous section, we have learned that finite state generators are simple computing machines that output a sequence of symbols. You will often find the notion of an output tape the symbols are written on. A finite state recognizer in turn is a simple computing machine that reads (or at least tries to read) a sequence of symbols from an input tape . That is only a small difference: Finite state generators and finite state recognizers are exactly the same kind of machine. Just that we are using them to output symbols in one case and to read symbols in the other case. The general term for such machines is finite state automaton (FSA ) or finite state machine (FSM ). But let's have a closer look at what it means for a finite state automaton to recognize a string of symbols.

An FSA recognizes (or accepts) a string of symbols (or word) if starting in an intial state, it can read in the symbols one after the other while making transitions from one state to another such that the transition reading in the last symbol takes the machine into a final state. That means an FSA fails to recognize a string if:

1. it cannot reach a final state; or

2. it can reach a final state, but there are still unread symbols left over when it does

So, this machine

recognizes laughter. For example, it accepts the word ha! by going from state 1 via state 2 and state 3 to state 4. At that point it has read all of the input and is in a final state. It also accepts the word haha! by making the following sequence of transitions: state 1, state 2, state 3, state 2, state 3, state 4. Similarly, it accepts hahaha! and hahahaha! and so on. However, it doesn't accept the word haha -- although it will be able to read the whole input (state 1, state 2, state 3, state 2, state 3). The problem is that it will end up in a non-final state without anything left to read that could take it into the final state. Also, it does not accept hoho!. The reason is that with this input, it won't be able to read the whole input (there is no transition that allows reading an o).

So, when used in recognition mode, this machine recognizes exactly the same words that it generates when used in generation mode. This is something which is true for all finite state automata and we can make it more precise:

• A formal language is a set of strings.

• The language accepted (or recognized) by an FSA is the set of all strings it recognizes when used in recognition mode.

• The language generated by an FSA is the set of all strings it can generate when used in generation mode.

• The language accepted and the language generated by an FSA are exactly the same.