July 18, 2019 , , ,

1. Construct finite state automata (DFA) that ends with abb

Solution :
Σ: inputs = {a, b}
          q0 = initial state
          q1 = string ends with a
          q2 = string ends with ab
          q3 = string ends with abb

Q: set of all states (q0, q1, q2, q3)
F: Final State 
 
Transition Matrix
  f
    a b
ε q0 q1 q0
a q1 q1 q2
ab q2 q1 q3
abb q3 q1 q0
Transition Graph


2. Construct finite state automata (DFA) that ends with aab

Solution :
Σ: inputs = {a, b}
          q0 = initial state
          q1 = string ends with a
          q2 = string ends with aa
          q3 = string ends with aab

Q: set of all states (q0, q1, q2, q3)
F: Final State 
 Transition Matrix
  f
    a b
ε q0 q1 q0
a q1 q2 q0
aa q2 q2 q3
aab q3 q1 q0
Transition Graph


3. Construct finite state automata (DFA) that ends with aba

Solution :
Σ: inputs = {a, b}
          q0 = initial state
          q1 = string ends with a
          q2 = string ends with ab
          q3 = string ends with abb

Q: set of all states (q0, q1, q2, q3)
F: Final State 

   Transition Matrix
  f
    a b
ε q0 q1 q0
a q1 q1 q2
ab q2 q3 q0
aba q3 q1 q2
Transition Graph


4. Construct finite state automata (DFA) that ends with aabb

Solution :
Σ: inputs = {a, b}
          q0 = initial state
          q1 = string ends with a
          q2 = string ends with aa
          q3 = string ends with aab
         q4 = string ends with aabb

Q: set of all states (q0, q1, q2, q3, q4)
F: Final State 

  Transition Matrix
  f
    a b
ε q0 q1 q0
a q1 q2 q0
aa q2 q2q3
aab q3 q1 q4
aabb q4 q1 q0
Transition Graph