Finite Automata #

Nondeterministic Finite Automata #

Nondeterministic finite automata (NFA) have no restrictions on the labels of their edges. A symbol can label several edges out of the same state, and , the empty string, is a possible label.

Example #

The transition graph for an NFA recognizing the language of regular expression (a|b)*abb. It is similar to regular expressions that describe languages of real interest.

For more details on the regular expression, check out the note on the Unix programming class.

Transition tables #

We can also represent an NFA by a transition table, whose rows correspond to states, and whose columns correspond to the input symbols and . The entry is the transition state corresponding to the current state and the input. If the state-input pair doesn't exist, we put in the entry.

Example #

The transition table for the NFA graph above.

Deterministic Finite Automata #

A deterministic finite automaton (DFA) is a special case of an NFA where:

1. There are no moves on input .
2. For each state and input symbol , there is exactly one edge out of labeled .

Example #

The transition graph for an DFA recognizing the language of regular expression (a|b)*abb.

The transition graph for floating point

Define digit as [0-9] in the regular expression