Theoretical CS

4.2 Deterministic Finite Automata

One use of graphs is to visually represent theoretical machines called deterministic finite automata (DFA). DFAs are simple models of computation that fall under the broader category of state machines.


You can represent a DFA using a directed graph; each vertex represents a state, and each directed edge represent a possible transition to another state. This graph represents the DFA’s program, which either accepts or rejects an input string.

We will study how to use these graphs to write DFA algorithms.


We will also quickly touch on nondeterministic finite automata (NFA), which are very similar to DFAs. The difference is that each state can have multiple transitions for each input, as opposed to DFAs which can only have a unique transition for each input.

<< 4.1 Trees and Graphs 4.3 Turing Machines >>