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.
