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}

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