FOR FREE MATERIALS

Design a DFA for Language: “Not start with ‘a’ or not end with ‘b’”

∑ = {a, b}

Answer:

When language starts with ‘NOT’ then the negation machine is quite difficult to design in that case we use the complement of the given language.

${\mathit{L}}_{\mathbf{1}}\mathbf{:}$ Not Start with ‘a’ or not end with ‘b’.

Complement of  ${\mathit{L}}_{\mathbf{1}}$ machine:

${{\mathbf{L}}_{\mathbf{1}}}^{\mathbf{C}}\mathbf{:}$ Start with a and end with b [At complement Not is remove and ‘OR’ replace with AND]

Now we design a machine for ${{\mathbf{L}}_{\mathbf{1}}}^{\mathbf{C}}\mathbf{:}$ Start with a and end with b.

Now to get the original machine of ${\mathit{L}}_{\mathbf{1}}\mathbf{:}$ Not Start with ‘a’ or not end with ‘b’ complement the above machine i.e. machine of ${{\mathbf{L}}_{\mathbf{1}}}^{\mathbf{C}}$. 

Procedure to complement a machine:

Change all non-final states to final states and corresponding final states to non-final states of the machine. All the moves and directions of the machine remain the same.

Example: 

So, complement the ${{\mathbf{L}}_{\mathbf{1}}}^{\mathbf{C}}$ machine to get the desired machine of ${\mathit{L}}_{\mathbf{1}}\mathbf{:}$ Not Start with ‘a’ or not end with ‘b’.

${\mathit{L}}_{\mathbf{1}}$ = {λ, a, b…..}

Regular Expression L = λ + b(a + b)* + (a + b)* a 

Grammar of ${\mathit{L}}_{\mathbf{1}}\mathbf{:}$

S → aA | bC | λ

A → aA | bB | λ

B → bB | aA

C → aA | bC | λ

Note: Complement of DFA is possible but complement is not possible for NFA.