Design a machine of the following language:

L = set of all string no consecutive 1’s where = {0, 1}.

Given a language, L = set of all string no consecutive 1’s i.e. 11.

But it is not very easy to design the above machine because the language of this machine has negation. Negation machine is quite difficult to design.

We previously discussed how to design the negation machine.

Steps to design a negation machine:

Step 1. First, do complement of the given negation language L to a non-negative language ${\mathbf{L}}^{\mathbf{C}}$.

L= Set of all string no consecutive 1’s

${\mathbf{L}}^{\mathbf{C}}$Set of all string containing two consecutive 1’s

Step 2. Design a machine for ${\mathbf{L}}^{\mathbf{C}}$ = Set of all string containing two consecutive 1’s

${\mathbf{L}}^{\mathbf{C}}$ = {11, 011, 110, 111, 1111, ……}

Regular Expression RE(0 + 1)* 11 (0 + 1)*

M1: Machine Set of all string containing two consecutive 1’s

Another Regular Expression from machine = (010)*1(0 + 1)*

Step 3. The complement of M1 for the original machine i.e. set of all strings no two consecutive ones.

M2: Machine “Set of all string containing two consecutive 1’s

RE = (0 + 10)* + (0 + 10)*1 = (0 +10)* (λ + 1) = (λ + 1) (0 + 10)*

See the RE = (0 + 10)*is the all combination of strings now we want all string but no consecutive 1’s. Every time when 1 is coming and we put zero (0) be for or after then never consecutive 1’s is possible.

(0 + 10)* in this the last zero prevents making consecutive 1’s because every time when 1 came the zero is coming after that. So, never consecutive 1’s is possible.

But here (0 + 10)* every time string which ends with 0 but there is no string end start with 1. So we put (λ + 1). RE = (0 + 10)*(λ + 1), now string end with 0 or end with 1’s.