Deterministic Finite Automata (DFA)

Definition of Deterministic Finite Automata

Deterministic Finite Automata (DFA) consists of 5 tuples {Q, ∑, q, F, δ}. 
Q : set of all states.
∑ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X ∑ --> Q.

In a DFA, for a particular input character, machine goes to one state only. A transition function is define on every state for every input symbol. Also in DFA null (or ε) move is not allowe, i.e., DFA can not change state without any input character.

For example, below DFA with ∑ = {0, 1} accepts all strings ending with 0.

One important thing to note is, there can be many possible DFAs for a pattern. A DFA with minimum number of states is generally preferred.

 

Some Important Points:

1. Every DFA is NFA but not vice versa.
2. Both NFA and DFA have same power and each NFA can be translated into a DFA.
3. There can be multiple final states in both DFA and NFA.
4. NFA is more of a theoretical concept.
5. DFA is used in Lexical Analysis in Compiler.

Limitations of Finite Automata

The defining characteristic of FA is that they have only a finite number of states. Hence, a finite automata can only “count” (that is, maintain a counter, where different states correspond to different values of the counter) a finite number of input scenarios.

There is no finite automaton that recognizes these strings:

• The set of binary strings consisting of an equal number of 1’s and 0’s
• The set of strings over ‘(‘ and ‘)’ that have “balanced” parentheses

The ‘pumping lemma’ can be used to prove that no such FA exists for these examples.

Read: What is Non Deterministic Finite Automata?