Automata - Deterministic finite-state automata (DFA)


A Deterministic finite-state automata (DFA) is a finite automaton that cannot be in more than one state at any one time.

The term deterministic refers to the fact that on each input there is one and only one state to which the automaton can transition from its current state.

The inverse of Deterministic finite-state automata (DFA) is Nondeterministic finite-state automata (NFA) that may be in several states at once.


A DFA is denoted in the Five tuple notation as being a set of the following element.

<MATH> A = (Q, \sigma, \delta, q0, F) </MATH> where:

  • A is the name of the DFA
  • Q is its set of states
  • <math>\sigma</math> is its input symbols
  • <math>\delta</math> is its transition function
  • q its start state
  • F its set of accepting states


A finite automaton has the following function composition property

For the deterministic finite automata q, if the input string <math>s = y+z</math> , then processing a string s composed of two strings y and z is the same than processing first y then processing z.

<MATH>\delta(q,s) = \delta(\delta(q,y),z)</MATH>

where <math>\delta</math> is the state of an automaton q after processing a string (here s, y or z)

Documentation / Reference

Powered by ComboStrap