Deterministic Finite Automaton (DFA) Solved Example
11. Design DFA for a language L= {w | length of w is multiple of 3) over Σ={a,b}
DFA M11 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1, q2}
- Σ : {a, b}
- δ = Q × Σ -> Q =
- δ(q0, a) = q1
- δ(q0, b) = q1
- δ(q1, a) = q2
- δ(q1, b) = q2
- δ(q2, a) = q0
- δ(q2, b) = q0
- q0 : q0.
- F : {q0}
Note: The transition function can also be described with a transition table.
12. Design DFA for a language L= {w | w is an empty string or a string that ends with 1) over Σ={0,1}
DFA M12 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1}
- Σ : {0, 1}
- δ = Q × Σ -> Q =
- δ(q0, 0) = q0
- δ(q0, 1) = q1
- δ(q1, 0) = q0
- δ(q1, 1) = q1
- q0 : q0.
- F : {q0}
Note: The transition function can also be described with a transition table.
13. Design DFA for a language L= {w | contains neither 00 nor 11) over Σ={0,1}
DFA M13 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1,q2,q3}
- Σ : {0, 1}
- δ = Q × Σ -> Q =
- δ(q0, 0) = q2
- δ(q0, 1) = q1
- δ(q1, 0) = q2
- δ(q1, 1) = q3
- δ(q2, 0) = q3
- δ(q2, 1) = q1
- δ(q3, 0) = q3
- δ(q3, 1) = q3
- q0 : q0.
- F : {q1.q2}
Note: The transition function can also be described with a transition table.
14. Design DFA that accepts odd binary numbers. over Σ={0,1}
DFA M14 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1,q2,q3}
- Σ : {0, 1}
- δ = Q × Σ -> Q =
- δ(q0, 0) = q3
- δ(q0, 1) = q1
- δ(q1, 0) = q2
- δ(q1, 1) = q1
- δ(q2, 0) = q2
- δ(q2, 1) = q1
- δ(q3, 0) = q3
- δ(q3, 1) = q3
- q0 : q0.
- F : {q1}
Note: The transition function can also be described with a transition table.
