Languages, Finite State Machines

Finite State Machines

Like grammars, finite state machines define languages. The finite state machine is often abbreviated fsm; however, some texts use the term finite state automatan, or fsa. I prefer fsm, which is consistent with turing machine, or tm.

An fsm is a virtual device that manipulates a candidate string, one character at a time, and determines whether that string is in the language implemented by the machine. The simplest state machine reads the string exactly once, and has no memory, only registers. It is therefore a finite state machine.

An fsm is defined by a set of states and a transition function that maps state/input pairs into states. In this state, reading this character, move to that state and advance to the next character.

Some states are designated "final" states, and strings that leave the fsm in one of these final states are, by definition, in the language.

One state is designated the start state. When the start state is also a final state, E is necessarily in the language.

Example: The following 4-state machine defines binary strings with an even number of 1's and 0's. States are abcd, and input characters are 0 1. State a is both the start state and the final state

            0 1
        a → b c
        b → a d
        c → d a
        d → c b

Nondeterministic FSM

An fsm is nondeterministic if it is confronted with several choices when processing each character. Thus the transition function of a nondeterministic fsm maps state/input pairs into sets of states. The machine somehow traverses all possible paths in parallel. In addition, E transitions are permitted, allowing the machine to change states without reading an input character. A string is accepted by an nfsm if one of its parallel transition sequences leads to a final state.

this seems to add a great deal of power, but in fact it does not. Any nfsm can be emulated by an fsm with more states. Start with an nfsm containing n states x₁ x₂ x₃ etc, and construct a deterministic fsm with 2ⁿ states as follows. Each state in the new fsm corresponds to a unique combination of states in the original nfsm. The initial state y₀ corresponds to the union of the initial state x₀ and all other x_j states that are accessible from x₀ via E transitions. The state y_i in the fsm is a final state if any of the corresponding x_j states, represented by y_i, is a final state in the original nfsm. To determine the transition function f(y_i, C), apply C to each corresponding x_j state, and bring in any new states that are accessible via E transitions. The combination of all these states determines a particular y_k. Thus state y_i, reading character C, moves to state y_k.

By induction on string length, any string that leaves the constructed fsm in state y_i also leaves the original fsm in any of the corresponding states x_j. One machine says yes to the input word iff the other one does. Therefore nondeterministic fsms are no more powerful than their deterministic counterparts.