Deterministic Finite Automaton (DFA) Solved Example
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.
