CLASS 15: CONSTRUCTION OF FINITE AUTOMATA (FA)

3. Construct a DFA which accept a string of a's and b's start and end with a such as  aa, aaa, aba, abba, etc.

Solution : 

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string must start and end with a.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it.

let we start

Case I: Input string = aa or aaa or aaaaa or aaaaaa etc.

Case II: Input string = aba 

Case III: Input string = ababa 

Case IV: Input string = abaa 

Case V: Input string = abaaba 

Formal Definition : 

Q = {q0, q1, q2}

Σ = {a, b}

q0 = q0

F = {q2}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE V we get final graph.