Class 17 - CONSTRUCTION OF FINITE AUTOMATA (FA)

5. Constrict a DFA which accept a string of a's and b's contain even number of a's followed by odd number of b's. such as (b, aab, aabbb etc.)

Solution:

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string having even number of a's and odd number of b's.

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

let we start

Case I: Input string = b / aab

Case II: Input string = b / aab /aabbb /aaaabbb 

Case III: Input string = Note there are some rejected states such as (aba / aabba / aaba etc)

Formal Definition :

Q = {q0, q1, q3, q4, q5}

Σ = {a,b}

q0 = q0

F = {q3}

δ = 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.