Deterministic Finite Automata

Deterministic Finite State machines or Deterministic Finite Automata (DFA) are one of the most basic forms of automata, although there are many forms of automata, some more complex and powerful, this tutorial will only be centered around the DFA.

A deterministic finite automaton consists of five main parts:

  • a finite set of states Q
  • a set of input or alphabet \Sigma
  • a set of final states, F, F \subset Q
  • an initial state q_0 \in Q
  • a transition function \delta : Q \times \Sigma \rightarrow Q

DFA is formally defined as a quintuple M = <Q, \Sigma, \delta, q_0, F>.

A DFA will always start in initial state, it will then be fed a string of input characters causing it to change states. Each character in the string will cause the DFA to change according to its state and the transition function. When the whole string is consumed and the DFA’s state is a final state then the string is consider to be accepted by the DFA, if the internal state is not a final state then the DFA is said to have rejected the string.

Previous | Next

  1. What is a Finite State Machine?
  2. Deterministic Finite Automata
  3. Examples of DFA part 1
  4. Examples of DFA part 2
  5. Examples of DFA part 3
  6. Combining DFAs
  7. Limits and Languages of DFAs
  8. Applications

Filed Under: Crash Courses, Computer Science

Sources Used

  • Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman

Sharing the Wonder