deterministic finite automaton

A deterministic finite automaton (or DFA) is a deterministic automaton with a finite input alphabet and a finite number of states. It can be formally defined as a 5-tuple (S,Σ,δ,q0,F), where

  • S is a non-empty finite setMathworldPlanetmath of states,

  • Σ is the alphabet (defining what set of input strings the automaton operates on),

  • δ:S×ΣS is the transition function,

  • q0S is the starting state, and

  • FS is a set of final (or accepting states).

A DFA works exactly like a general automaton: operationMathworldPlanetmath begins at q0, and movement from state to state is governed by the transition function δ. A word is accepted exactly when a final state is reached upon reading the last (rightmost) symbol of the word.

DFAs represent regular languages, and can be used to test whether any string in Σ* is in the languagePlanetmathPlanetmath it represents. Consider the following regular language over the alphabet Σ:={𝚊,𝚋} (represented by the regular expressionMathworldPlanetmath aa*b):

<S> ::= aA
<A> ::= b|𝚊A

This language can be represented by the DFA with the following state diagramPlanetmathPlanetmath: