Design a machine of the following language: 


L = Exactly two a’s and two b’s where  = {a, b}.




From the given language it is clear that it is two grade of machine


Firstly we design a machine for exactly two a’s which same design as exactly two b’s. So, anyone we can design as an example lets design “exactly two a’s”.

So, as per the given language L = exactly two a’s and two b’s. “exactly two a’s” requires 3 states (we are not considered trap state qt), and same as “exactly two b’s” requires 3 states. So, the total grade of states require for L = exactly two a’s and two b’s is 3 x 3 = 9


We can take a’s state as horizontal direction and b’s state as vertical i.e. three state as horizontal for a and three state as vertical for b.


And apart from 9 states, we require one extra state which identifies trap state qt for all. 


L = exactly two a’s AND two b’s, so as we know AND means intersection i.e. common states between all states of exactly two a’s and all states of exactly two b’s. 


Minimum NFA = 9 states,  Minimum DFA = 10 states (one step for trap state).


If there m a’s and n b’s then

        Minimum NFA = (m+1) (n+1) ,  Minimum DFA = (m + 1) (n + 1) + 1