# CREATE OWN LIBRARY

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

∑ = {a, b}

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.

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

Complement of  ${{\mathbit{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 ${{\mathbit{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 ${{\mathbit{L}}}_{{\mathbf{1}}}{\mathbf{:}}$ Not Start with ‘a’ or not end with ‘b’.

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

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

Grammar of ${{\mathbit{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