Automata Theory Tutorial
Classification of Grammars
Regular Grammar
Context-Free Grammars
Pushdown Automata
Turing Machine
Decidability
Automata Theory Useful Resources
Selected Reading
- Moore & Mealy Machines
- DFA Minimization
- NDFA to DFA Conversion
- Non-deterministic Finite Automaton
- Deterministic Finite Automaton
- Automata Theory Introduction
- Automata Theory - Home
Classification of Grammars
Regular Grammar
- DFA Complement
- Pumping Lemma for Regular Grammar
- Constructing FA from RE
- Regular Sets
- Regular Expressions
Context-Free Grammars
- Pumping Lemma for CFG
- Greibach Normal Form
- Chomsky Normal Form
- CFG Simplification
- CFL Closure Properties
- Ambiguity in Grammar
- Context-Free Grammar Introduction
Pushdown Automata
- PDA & Parsing
- PDA & Context Free Grammar
- Pushdown Automata Acceptance
- Pushdown Automata Introduction
Turing Machine
- Linear Bounded Automata
- Semi-Infinite Tape Turing Machine
- Non-Deterministic Turing Machine
- Multi-Track Turing Machine
- Multi-tape Turing Machine
- Accepted & Decided Language
- Turing Machine Introduction
Decidability
- Post Correspondence Problem
- Rice Theorem
- Turing Machine Halting Problem
- Undecidable Language
- Language Decidability
Automata Theory Useful Resources
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
DFA Complement
DFA Complement
If (Q, ∑, δ, q0, F) be a DFA that accepts a language L, then the complement of the DFA can be obtained by swapping its accepting states with its non-accepting states and vice versa.
We will take an example and elaborate this below −
![DFA Accepting Language L](/automata_theory/images/dfa_accepting_language_l.jpg)
This DFA accepts the language
L = {a, aa, aaa , ............. }
over the alphabet
∑ = {a, b}
So, RE = a+.
Now we will swap its accepting states with its non-accepting states and vice versa and will get the following −
![DFA Accepting Complement Language L](/automata_theory/images/dfa_accepting_complement_language_l.jpg)
This DFA accepts the language
Ľ = {ε, b, ab ,bb,ba, ............... }
over the alphabet
∑ = {a, b}
Note − If we want to complement an NFA, we have to first convert it to DFA and then have to swap states as in the previous method.
Advertisements