Design a machine of the following language: 


where = {a, b}




As per the language given,

(Language containing strings with exactly 3 lengths).


So, to design a machine number of states will be required 3 + 1 = 4.

Note:  n length string then the no. of the state is (n +1)



Regular Expression 



Same way we can design,


Now machine of language containing strings having at least 2 lengths L = {aa, bb, aaa, bbb, ……} 


Regular Expression 


We can write as,


Regular Expression of Language containing at least n length string:


at least 3 length string.


at least 2 length string 


or, we can write as, 


So, look carefully what is the complement of L = {ω | |ω| ≥ 3}  at least 3 length string

(L = {ω | |ω| ≥ 3})’  = (L = {ω | |ω| < 3}) or one can rewrite (L = {ω | |ω| ≤ 2})


Now (L = {ω | |ω| < 3}) or (L = { ω | |ω| ≤ 2 }) is at most 2 lengths strings.


So, it is clear that at most 2 length string is a complement of at least 3 length string.   


Firstly, we design a machine M1 of at least 3 length string i.e. L = { ω | |ω| ≥ 3} ∑ = {a, b}.

M1: Machine “At least 3 lengths strings


Now if we take a complement of machine M1 (at least 3 lengths strings) then we get a machine M2 which at most 2 lengths string.

M2: Machine “At most 2 lengths strings


Strings accepted by the machine M2 like L = {λ, a, b, aa, bb……}. The string will be zero length, one length, and two length strings. 



we can write as (λ + a + b)2


How derive it as (λ + a + b)2 - see (λ + a + b) (λ + a + b) - from this we get all the combinations of strings accepted by machine M2. Like we can λ, a, b, aa, bb……



Regular Expression of at most n length string is