Home > Theory Of Computation > DFA Example : Complement Of Finite Automata

DFA Example : Complement Of Finite Automata

Complement Of Finite Automata Means The Finite Automata Which Is Obtained By Interchanging Final And Non-Final States Is Known As Complement Of Finite Automata.

In This Concept, I’ll Change Final States To Non-Final To Final State And Final To Non-Final State.

By Doing This The Language Changes.



M Supports L Language


The String Which Comes In Language L Are Accepted By Machine M


L Belongs To Sigma Star

Σ* Means Universal Set Of Strings(All The Strings)

L⊆Σ* Means The Strings Which Are Accepted By Language Comes Under ‘L’ Not All Strings Comes Under ‘L’


M→L⊆Σ* Means Machine M Accepts Strings Which Are Belongs To ‘L’ And L Is The Language(Set Of Strings) Which Are Subset Of Universal Set Of Strings i.e Σ* (Sigma Star)

Then What Is Complement Of Finite Automata?

If I Give Complement For Machine ‘M’ That Becomes M1

M1→L1= Σ*- L

MIs The Machine Which Accepts The Language L1

L1= Σ*- L


This Machine MAccepts The Language L1

And L1  Is Universal Set Of Strings Language.


M1→L1= Σ*- L


I Hope You Understood The Difference Between Machine M And Machine M1


  1. Σ={a,b}

L=String Starts With ‘a’

This Is (M) Machine Example.


     2. Σ={a,b}

L=String Does Not Start With ‘a’


This Is M(Machine Complement) Example In M1

The Non-Final States Becomes Final State Including Dead State And Final States Becomes Non-Final State.






  • L(FA)∩l(FA1)=Φ
  • L(FA)∪(FA1)=Σ*
  • M→n states k final states
  • M1→ n states n-k final states




One thought on “DFA Example : Complement Of Finite Automata

Leave a Reply