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-Automata(DFA)

L-Language

M Supports L Language

 

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

L⊆Σ*

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.

M→L⊆Σ*

M1→L1= Σ*- L

 

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

Example

  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.

 

Cross-Check

baa

 

Remember

  • 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