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.

L1: Not Start with ‘a’ or not end with ‘b’.


Complement of  L1 machine:

L1C: Start with a and end with b [At complement Not is remove and ‘OR’ replace with AND]


Now we design a machine for L1C: Start with a and end with b.

Now to get the original machine of L1: Not Start with ‘a’ or not end with ‘b’ complement the above machine i.e. machine of L1C


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.




So, complement the L1C machine to get the desired machine of L1: Not Start with ‘a’ or not end with ‘b’.


L1 = {λ, a, b…..}


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


Grammar of L1:

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