Q = {q0 , q1} ∑ = {a,b} q1 is the final state and q0 is the initial state 

Q X ∑ = {(q0, a), (q0, b), (q1, a), (q1, b) }





∑ = {a,b}

It is not DFA because has no all moves i.e. q0 has no move for ‘a’ (input). As per the machine design if ‘a’ input move is not possible for q0 state then create a trap state to make a move for that state.


If there are no real states (move) for any alphabet (input) in that case create a trap state to make a  move for that state. Because in DFA all inputs move must be present for every state. Trap state is never part of the machine.


DFA Machine (M) with Trap State


Language of the above machine:


L(M) = {b, ba, ba*, bbb, …. baabb,  baaaa….}

i.e. L(M) = {All strings started with symbol b and having odd number of b’s}

DFA has no infinite capacity storage, finite memory in form of state.

If we take        

                        2 states – 1bit

                        4 states – 2bit

                       2n states – n bit

So, if the bit is finite then definitely the number of states is also finite.



 Identify this machine is DFA or not.  ∑ = {a, b}

It is not a DFA, no move for a at q1 state.
Now it is DFA.


Language of the above machine M:


L = {a, ab, abbb, abbbb, ….} here L is followed by b

Find the correct language of above DFA?

1.L1 = abb*

2.L2 = ab*

3.L3 = (a + b)* = Σ* where b* = {λ, b, bb, bbb, bbbb ….} 




Option 1: L1= {ab, abb, abbb, abbbb….} all strings which accepted by the machine but one string which accept by the above machine but never in L1. So, L1 is not a Language of M. {a ∊ ω, a ∉ L1L1 ⊂ L(M) which fails the second condition of accepting L.


Option 2: (a + b)* = Σ*  it is not L(M) because it fails first condition of acceptation L


  but b is not an accepting string.

Option 3: Actually (a + b)* means all string generated by ‘a’ and ‘b’ i.e. universal set of strings generated by ‘a’ and ‘b’.

L2 = ab*

L2 = {ab, abb, abbb, abbbb….} here two condition are true so, L(M) = L2


So, option 2 is correct answer.




∑ = {a, b}   

Language of the above machine: L(M) = (a+b)*