Deterministic Finite Automata

The term Deterministic means the uniqueness of the computation. It is a finite state machine that either accepts or rejects strings of symbols, and for each input string it returns a unique computation. It has a set of states and rules for going from one state to another, depending on the input symbol. When the machine is in a given state and reads the next input symbol, we know what the next state will be - it is determined. It reads only one input symbol at a time from the tape, and after that it decides whether to accept or reject the input.

A DFA is defined as an abstract mathematical concept, but is often implemented in hardware and software for solving different specific problems such as lexical analysis and pattern matching.

Parts of DFA

A deterministic finite automata has three parts-

• A tape to hold the input string.
• A tape head to read the input symbols.
• A control that contains three main parts – set of start states, set of transition functions and final states.

Formal Definition of DFA

A DFA is five tuple, consisting of

(Q, ∑, δ, q0, F)

Q- A finite set of states.
∑- Alphabet of input symbols.
δ- A transition function that takes as argument a state and a symbol and returns a state.

Q×Σ→Q

q0- A start state.
F- A set of final or accept states.

Represent DFA with Transition Table

Here is an example of DFA using a transition table and a graph. The → indicates the start state and the * indicates the final state.

			0	1
		→q0	q1	q0
		q1	q1	q2
		*q2	q2	q2

DFA transition diagram of above transition table.

The formal DFA of the above example is -

Q={q0, q1, q2}

Σ ={0,1}

q0(start state) = q0

δ:Q×Σ→Q

F(final state) = {q2}

Language accepted by DFA

The language L(M), accepted and recognized by a DFA is the set of all strings w accepted by M -

L(M) = {w ∈ Σ* | M accepts w}