FOR FREE YEAR SOLVED

Design a machine of the following language: 

Answer:

As per the language given,

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,

Or,

Regular Expression of Language containing at least n length string:

Now,

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. 

So, 

we can write as ${\mathbf{(}\mathbf{\lambda }\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{a}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{b}\mathbf{)}}^{\mathbf{2}}$

How derive it as ${\mathbf{(}\mathbf{\lambda }\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{a}\mathbf{ }\mathbf{+}\mathbf{ }\mathbf{b}\mathbf{)}}^{\mathbf{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