DFA is one of the classifications of Finite Automata.
Where each input symbol, one can determine the state to which the machine will move. As we can determine the state of the machine so, it is called a Deterministic Automaton. It can have a finite number of states.
A finite state machine that accepts or rejects finite strings of symbols and can only produce a single computation of the automaton for each input string.
A DFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −
Q is a finite set of states.
∑ is a finite set of symbols called the alphabet.
δ is the transition function where δ: Q × ∑ → Q
q0 is the initial state from where any input is processed (q0 ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).
A Non-deterministic Finite Automaton is like a deterministic finite automaton, except you have the possibility of going to more than one state from each current state.
| DFA | NFA | |
|---|---|---|
| 0 | For Every symbol of the alphabet, there is only one state transition in DFA. | We do not need to specify how does the NFA react according to some symbol. |
| 1 | DFA cannot use Empty String transition | NFA can use Empty String transition. |
| 2 | DFA can be understood as one machine. | NFA can be understood as multiple little machines computing at the same time. |
| 3 | DFA will reject the string if it end at other than accepting state. | If all of the branches of NFA dies or rejects the string, we can say that NFA reject the string. |
| 4 | DFA is more difficult to construct. | NFA is easier to construct. |
Suppose there is an NFA N < Q, ∑, q0, δ, F > which recognizes a language L. Then the DFA D < Q’, ∑, q0, δ’, F’ > can be constructed for language L as:
Step 1: Initially Q’ = ɸ.
Step 2: Add q0 to Q’.
Step 3: For each state in Q’, find the possible set of states for each input symbol using transition function of NFA. If this set of states is not in Q’, add it to Q’.
Step 4: Final state of DFA will be all states with contain F (final states of NFA)
References: w3schools, bilgisayarkavramları, GeeksforGeeks, images