Class 16 - CONSTRUCTION OF FINITE AUTOMATA (FA)

4. Construct a DFA which accept a string of a's and b's start and ends with the same symbol. such as ( aba, bab, a, b etc).

Solution : 

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

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

let we start

Case I: Input string = a or b 

Case II: Input string = aa or bb 

Case III: Input string = aabba /aaabbba or bbaab /bbbaaab 

Formal Definition :

Q = {q0, q1, q3, q4}

Σ = {a,b}

q0 = q0

F = {q1 , q2}

δ = Transition Table

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