In DFA, for a particular input character, the machine goes to one state only and it has finite number of states, the machine is called Deterministic Finite Machine.
- In DFA, there is only one path for specific input from the current state to the next state.
- In DFA, does not accept the null (or ε) move, i.e., the DFA cannot change state without any input character.
- In DFA, can contain multiple final states. It is used in Lexical Analysis in Compiler.
- In DFA, A transition function is defined on every state for every input symbol.
- In DFA, can have maximum N+1 number of states where N is the length of the string.
Formal Definition of DFA
A DFA can be represented by 5-tuples (Q, ∑, δ, q0, F)
Q: finite set of states
∑: finite set of the input symbols (alphabets)
δ: Transition function where δ: Q x ∑→Q
q0: initial state from where any input is processed (qoεQ)
F: final state of Q
Graphical Representation of DFA
A DFA can be represented by digraphs called state diagram. In which:
- Vertices represent states
- Arcs labeled with an input alphabet shows the transitions.
- Initial state is denoted by an empty single incoming arch (arrow).
- Final state is indicated by a double circle.
Example 1:
For example, below DFA with Σ = {0, 1} accepts all strings ending with 0.
In the following diagram, we can see that from state q0 for input 0, there is only one path which is going to q1. Similarly, from q1, there is only one path for input 1 going to q0.
Example 2:
Let Q = {a, b, c} -> Set of Finite States
∑ = {0, 1} -> Set of Strings
q0 = {a} -> Initial State
F = {c} -> Final State
Transition Function δ is shown by this table ↓
| Present State | Next State for Input 0 | Next State for Input 1 |
|---|---|---|
| a | a | b |
| b | c | a |
| c | b | c |
DFA Diagram for the above transition table
