DFA examples
1. Design DFA for a L= {w | w ends with 1) over Σ={0,1}
DFA M1 is = (Q, Σ, δ, q0, F)
Where
- Q : {q1, q2}
- Σ : {0, 1}
- δ = Q × Σ -> Q =
- δ(q1, 0) = q1
- δ(q1, 1) = q2
- δ(q2, 0) = q1
- δ(q2, 1) = q2
- q0 : q1.
- F : {q2}
Note: The transition function can also be described with a transition table.
2. Design DFA for a L= {w | w has length 2) over Σ={a,b}
DFA M2 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1, q2,q3}
- Σ : {a, b}
- δ = Q × Σ -> Q =
- δ(q0, a) = q1
- δ(q0, b) = q1
- δ(q1, a) = q2
- δ(q1, b) = q2
- δ(q2, a) = q3
- δ(q2, b) = q3
- δ(q3, a) = q3
- δ(q3, b) = q3
- q0 : q0.
- F : {q2}
Note: The transition function can also be described with a transition table.
3. Design DFA for a L= {w | w has exactly 2 a's) over Σ={a,b}
DFA M3 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1, q2,q3}
- Σ : {a, b}
- δ = Q × Σ -> Q =
- δ(q0, a) = q1
- δ(q0, b) = q0
- δ(q1, a) = q2
- δ(q1, b) = q1
- δ(q2, a) = q3
- δ(q2, b) = q2
- δ(q3, a) = q3
- δ(q3, b) = q3
- q0 : q0.
- F : {q2}
Note: The transition function can also be described with a transition table.
4. Design DFA for a L= {w | w has even length) over Σ={0,1}
DFA M4 is = (Q, Σ, δ, q0, F)
Where
- Q : {q2, q3}
- Σ : {0, 1}
- δ = Q × Σ -> Q =
- δ(q2, 0) = q3
- δ(q2, 1) = q3
- δ(q3, 0) = q2
- δ(q3, 1) = q2
- q0 : q2.
- F : {q2}
Note: The transition function can also be described with a transition table.
5. Design DFA for a L= {w | number of 0's in w is even.) over Σ={0,1}
DFA M5 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1}
- Σ : {0, 1}
- δ = Q × Σ -> Q =
- δ(q0, 0) = q1
- δ(q0, 1) = q0
- δ(q1, 0) = q0
- δ(q1, 1) = q1
- q0 : q0.
- F : {q0}
Note: The transition function can also be described with a transition table.
6. Design DFA for a L= {w | w has length <= 2} over Σ={0,1}
DFA M6 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1, q2,q3}
- Σ : {a, b}
- δ = Q × Σ -> Q =
- δ(q0, a) = q1
- δ(q0, b) = q1
- δ(q1, a) = q2
- δ(q1, b) = q2
- δ(q2, a) = q3
- δ(q2, b) = q3
- δ(q3, a) = q3
- δ(q3, b) = q3
- q0 : q0.
- F : {q0,q1,q2}
Note: The transition function can also be described with a transition table.
7. Design DFA that accepts all strings with odd number of a's, over Σ = {a, b}
DFA M7 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1}
- Σ : {a, b}
- δ = Q × Σ -> Q =
- δ(q0, a) = q1
- δ(q0, b) = q0
- δ(q1, a) = q0
- δ(q1, b) = q1
- q0 : q0.
- F : {q1}
Note: The transition function can also be described with a transition table.
8. Design DFA for a L= {w | w starts with ab) over Σ={a,b}
DFA M8 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1, q2,q3}
- Σ : {a, b}
- δ = Q × Σ -> Q =
- δ(q0, a) = q1
- δ(q0, b) = q3
- δ(q1, a) = q3
- δ(q1, b) = q2
- δ(q2, a) = q2
- δ(q2, b) = q2
- δ(q3, a) = q3
- δ(q3, b) = q3
- q0 : q0.
- F : {q2}
Note: The transition function can also be described with a transition table.
9. Design DFA for a L= {w | number of a's in w is less than or equal to two.) over Σ={a,b}
DFA M9 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1, q2,q3}
- Σ : {a, b}
- δ = Q × Σ -> Q =
- δ(q0, a) = q1
- δ(q0, b) = q0
- δ(q1, a) = q2
- δ(q1, b) = q1
- δ(q2, a) = q3
- δ(q2, b) = q2
- δ(q3, a) = q3
- δ(q3, b) = q3
- q0 : q0.
- F : {q0,q1,q2}
Note: The transition function can also be described with a transition table.
10. Design DFA for a L= {w | number of a's in w is greater than or equal to two.}
DFA M10 is = (Q, Σ, δ, q0, F)
Where
- Q : {q0, q1, q2}
- Σ : {0, 1}
- δ = Q × Σ -> Q =
- δ(q0, 0) = q1
- δ(q0, 1) = q0
- δ(q1, 0) = q0
- δ(q1, 1) = q1
- q0 : q0.
- F : {q0}
Note: The transition function can also be described with a transition table.
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.
