A tutorial on finite automata
DFA, a mathematical definition
An automaton, a language recognition device, can also be defined rigorously.
Definition
A deterministic finite state automaton is a quintuple <Q,I,delta,q0,F>; where:
-
Q is a finite set of states;
-
I is a finite set of input symbols;
-
delta is the next-state function delta:Q X I->Q;
-
q0 element of Q is the initial state;
-
F contained in Q is the set of final states (or accepting states).
The function delta: Q X I->Q can be extended to the domain Q X I*, defining the function delta* as follows:
delta*(q,lambda)=q for each q belonging to Q
delta*(q,xa)=delta(delta*(q,x),a) for each x belonging to I* and for each a belonging to I.
The language L(A) accepted or recognized by the automaton A is defined as the set of words accepted by A:
L(A) = { x| delta* (q0, x) belongs to F}
Back to Index