Theory of Computation Roadmap
A rigorous path from formal languages and finite automata to regular expressions, context-free grammars, pushdown automata, Turing machines and decidability. The roadmap connects every model with its language class, closure properties and proof techniques for university, GATE and competitive exams.
Learning outline
Expand a stage, choose a topic and start its Gate Smashers lectures.
01Formal-Language Foundations4 topics · 5 lectures0 / 5
▶TOC Scope & Model Hierarchy0 / 1 lectures
▶Alphabets, Strings & Languages0 / 2 lectures
▶Automata & Acceptance0 / 1 lectures
▶Grammars & Chomsky Hierarchy0 / 1 lectures
02Regular Languages & Automata6 topics · 23 lectures0 / 23
▶Deterministic Finite Automata0 / 1 lectures
▶DFA Construction Patterns0 / 7 lectures
▶DFA Equivalence & Minimization0 / 3 lectures
▶Nondeterministic Finite Automata0 / 3 lectures
▶NFA and ε-NFA Conversions0 / 4 lectures
▶Mealy & Moore Machines0 / 5 lectures
03Regular Expressions & Properties3 topics · 14 lectures0 / 14
▶Regular Expressions0 / 4 lectures
▶Pumping Lemma for Regular Languages0 / 1 lectures
▶Closure Properties of Regular Languages0 / 9 lectures
04Context-Free Languages6 topics · 13 lectures0 / 13
▶CFL & CFG Foundations0 / 4 lectures
▶Constructing Context-Free Grammars0 / 1 lectures
▶Derivations & Parse Trees0 / 2 lectures
▶Ambiguity & Recursive Grammars0 / 2 lectures
▶CFG Simplification0 / 2 lectures
▶CNF, GNF & CYK0 / 2 lectures
05Pushdown Automata2 topics · 3 lectures0 / 3
▶Pushdown Automata0 / 1 lectures
▶PDA Construction Patterns0 / 2 lectures
06Turing Machines & Computability4 topics · 6 lectures0 / 6
▶Context-Sensitive Languages & LBA0 / 1 lectures
▶Turing Machine Foundations0 / 1 lectures
▶Turing Machine Construction0 / 3 lectures
▶TM Variants & Equivalence0 / 1 lectures
07Decidability & Revision3 topics · 5 lectures0 / 5
▶Recursive & Recursively Enumerable Languages0 / 1 lectures
▶Decidability & Undecidability0 / 2 lectures
▶TOC Final Revision & Proof Map0 / 2 lectures
Topics covered in this roadmap
Use this stage-by-stage outline to understand the complete learning path before opening the interactive roadmap.
Formal-Language Foundations
TOC Scope & Model Hierarchy
See computation as a relationship among languages, grammars and machines. Establish the progression from finite automata to pushdown automata, linear-bounded automata and Turing machines.
Alphabets, Strings & Languages
Define the mathematical objects used throughout TOC. Work with alphabets, strings, length, concatenation and languages before describing any recognizing machine.
Automata & Acceptance
Understand an automaton as a state-based mathematical machine. Relate configurations, transitions and accepting states to the language recognized by a model.
Grammars & Chomsky Hierarchy
Describe languages through production rules rather than machines. Classify unrestricted, context-sensitive, context-free and regular grammars by restrictions and expressive power.
Regular Languages & Automata
Deterministic Finite Automata
Build the five-tuple definition of a DFA and simulate it on an input string. Translate a regular-language condition into states that preserve exactly the needed history.
DFA Construction Patterns
Design DFAs for prefixes, suffixes, positions, counts and modular properties. Combine independent conditions using product-state reasoning instead of ad hoc trial and error.
DFA Equivalence & Minimization
Determine whether states or complete DFAs accept the same future strings. Remove unreachable and equivalent states to obtain a minimal canonical machine.
Nondeterministic Finite Automata
Allow multiple possible transitions while preserving regular-language power. Understand acceptance as the existence of at least one successful computation path.
NFA and ε-NFA Conversions
Systematically convert nondeterministic machines into deterministic ones. Use subset construction and epsilon closure without losing or adding strings.
Mealy & Moore Machines
Study finite-state transducers that produce outputs rather than merely accepting input. Convert between state-output and transition-output forms while accounting for initial output behavior.
Regular Expressions & Properties
Regular Expressions
Describe regular languages algebraically using union, concatenation and Kleene star. Convert verbal conditions into expressions while respecting operator precedence and nullable behavior.
Regular Expression–Automata Equivalence
Connect algebraic and machine descriptions of regular languages. Use Thompson-style construction and state elimination as complementary conversion methods.
Pumping Lemma for Regular Languages
Use the unavoidable loop in a sufficiently long DFA computation to derive the pumping property. Apply the lemma by contradiction to prove selected languages are not regular.
Closure Properties of Regular Languages
Predict whether an operation preserves regularity and construct a recognizing machine when it does. Use closure results both to build languages and to support non-regularity proofs.
Regular-Language Decision Problems
Recognize the questions that are decidable for finite automata and regular expressions. Reduce emptiness, finiteness, equivalence and containment to reachable-state analysis.
Regular-Language Synthesis
Unify DFA, NFA, ε-NFA, regular expressions and regular grammars as equivalent views. Choose the representation best suited to construction, proof or decision-making.
Context-Free Languages
CFL & CFG Foundations
Move beyond finite memory to languages with nested and recursive structure. Define context-free languages through CFGs and distinguish them from deterministic CFLs.
Constructing Context-Free Grammars
Translate structural language rules into recursive productions. Separate alternatives, repetition and balanced dependencies while avoiding accidental over-generation.
Derivations & Parse Trees
Follow grammar productions as leftmost or rightmost derivations and represent the same structure as a parse tree. Distinguish derivation order from the underlying hierarchical syntax.
Ambiguity & Recursive Grammars
Identify grammars that give one string more than one parse tree or leftmost derivation. Rewrite common expression grammars while separating ambiguity from left recursion.
CFG Simplification
Remove productions and symbols that do not contribute to the intended language. Preserve epsilon carefully while eliminating null, unit and useless productions.
CNF, GNF & CYK
Transform CFGs into standard forms that simplify proofs and algorithms. Use Chomsky Normal Form with dynamic programming to decide bounded string membership through CYK.
Pumping Lemma for CFLs
Use repeated variables in sufficiently tall parse trees to derive the CFL pumping property. Apply coordinated pumping of two substrings to prove selected languages are not context-free.
CFG Reasoning Checkpoint
Consolidate grammar construction, derivations, ambiguity, simplification and normal forms. Use the checkpoint to choose between constructive and proof-oriented techniques.
Pushdown Automata
Pushdown Automata
Add an unbounded stack to finite-state control and obtain a recognizer for context-free languages. Track input, state and stack contents in every instantaneous description.
PDA Construction Patterns
Design stack behavior for counting, matching and nested structures. Decide when to switch phases and how nondeterminism guesses a midpoint or production choice.
CFG–PDA Equivalence
Relate context-free generation to stack-based recognition. Convert a CFG to a PDA and sketch how accepting computations can be encoded back into grammar variables.
Turing Machines & Computability
Context-Sensitive Languages & LBA
Introduce the language class between CFLs and recursively enumerable languages. Understand how a linear-bounded automaton restricts usable tape to the input length.
Turing Machine Foundations
Model general algorithmic computation using an infinite tape, a read–write head and finite control. Trace configurations and distinguish acceptance, rejection and non-halting behavior.
Turing Machine Construction
Build machines by composing marking, scanning, comparison and return-to-boundary routines. Use transition tables and diagrams to verify invariants on representative inputs.
TM Variants & Equivalence
Study common extensions that make machines easier to program without increasing computability. Separate changes in efficiency or convenience from changes in language-recognition power.
Decidability & Revision
Recursive & Recursively Enumerable Languages
Classify languages by whether a Turing machine always halts or may loop on nonmembers. Use complement behavior to understand the gap between decidable and recognizable languages.
Decidability & Undecidability
Ask whether a single terminating algorithm can answer every instance of a problem. Organize standard language questions by model and identify the boundary where undecidability begins.
Reductions, PCP & Rice’s Theorem
Prove undecidability by transforming a known hard problem into the target problem. Use mapping reductions, Post Correspondence Problem and Rice’s theorem with the correct direction and property conditions.
TOC Final Revision & Proof Map
Connect every language class to its grammar, automaton and key closure facts. Finish by choosing the right construction, pumping argument or reduction for each exam-style problem.