FOR FREE CONTENT

Subject Mock

Design a machine of the following language:

Answer:

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,

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 ${(λ + 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

Please Login to Bookmark