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,\mathrm{\Sigma },\delta ,q_0,F)$, where

• $S$ is a non-empty finite set of states,

• $\mathrm{\Sigma }$ is the alphabet (defining what set of input strings the automaton operates on),

• $\delta :S\times \mathrm{\Sigma }\to S$ is the transition function,

• $q_0\in S$ is the starting state, and

• $F\subseteq S$ is a set of final (or accepting states).

A DFA works exactly like a general automaton: operation begins at $q_0$, and movement from state to state is governed by the transition function $\delta$. 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 ${\mathrm{\Sigma }}^{*}$ is in the language it represents. Consider the following regular language over the alphabet $\mathrm{\Sigma }:=\{𝚊,𝚋\}$ (represented by the regular expression aa*b):

$\text{::=}$$\text{a}A$

$\text{::=}$$b|𝚊A$

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