### DFA / Deterministic Finite Automaton

DFA

• In DFA, every state will have a single transition for every symbol.

• ϵ- moves is not accepted in DFA

• So, the transition table will not have ø

1. Construct DFA with its transition graph and transition table for the RE (0+1)* 01
Here , Σ= {0,1}

Transition graph

Transition table

 0 1 qo q1 q0 q1 q1 q2 q2* q1 q0

Note:
In DFA, each entry of the transition table will have exactly one entry

1. Construct DFA with its transition graph and transition table for the RE (a+b)* abb
Here, Σ= {a,b}

Transition graph

Transition table

 a b q0 q1 q0 q1 q1 q2 q2 q2 q3 q3* q1 q0
1. Construct DFA with its transition graph and transition table for the RE (a | b)* abba
Here, Σ= {a,b}

​​​​​​​Transition graph

Transition table

 a b q0 q1 q0 q1 q1 q2 q2 q1 q3 q3 q4 q0 q4* q2 q0
1. Construct DFA with its transition graph and transition table for the set of strings over {0,1} whose length is divisible by 4.

Transition graph

Transition table

 a b q0* q1 q1 q1 q2 q2 q2 q3 q3 q3 q0 q0
1. Construct DFA with its transition graph and transition table for the regular expression
a b(a | b)*

Transition graph

Transition table

 a b 1 2 DS 2 2 3 3* DS DS DS DS DS