Theory of Computation
27 articles in this topic
Decidability in Regular Languages: DFA Tests, Worked Example and Exam Traps
Learn why DFA decision problems halt, how graph searches settle key language properties, and how a product automaton exposes the counterexample 10.
Closure Properties of Regular Languages: DFA Constructions and Exam Traps
Learn why regular languages remain regular under major operations. Build one product DFA, trace two strings, and compare the constructions operation by operation.
NFA Basics and Design: Build and Trace Nondeterministic Automata
Learn how an NFA branches, trace complete state sets, handle epsilon-closure, and convert a worked three-state machine into its reachable-subset DFA.
Chomsky Hierarchy Explained: Grammar Types, Worked Classification and Exam Traps
Learn how to test a grammar from Type 3 outwards, distinguish all four production classes, classify a complete grammar, and derive its strings step by step.
Turing Machine Basics and Design: Step-by-Step Worked Example for GATE
Build a deterministic single-tape TM that decides L = {0^n1^n | n >= 1}. Follow every move on 0011, test rejection cases, and connect the design to correctness and halting.
Simplification of CFG: Eliminate Epsilon, Unit and Useless Productions Step by Step
Learn the safe order for simplifying a context-free grammar. One example tracks every production through epsilon removal, unit closure, and useless-symbol removal.
Backus-Naur Form (BNF) Explained: Grammar Rules, Worked Derivations and Exam Traps
Learn to read BNF as a grammar, not as punctuation. Follow complete derivations, compare ambiguous parses, and see how recursion affects parsing.
Complexity Theory in Theory of Computation: P, NP, NP-Completeness and Worked Examples
Build complexity theory from input encoding upwards, then test each idea through a verified certificate and a complete 9-vertex reduction graph.
Closure Properties of Regular, Context-Free and Recursive Languages for GATE: The Complete Table with MSQ Drills
Learn the closure table through the few cells that cause most mistakes, then test the logic on four solved MSQ statements.
Pushdown Automata and CFG: Construction, Stack Traces and CFL Tests
Build a CFG and PDA for one language, trace both, convert the grammar, and settle the main CFL property traps with proofs.
Theory of Computation for GATE: Syllabus Map, Weightage Audit and Preparation Order
Map the official Theory of Computation syllabus, audit its completed GATE 2026 paper weightage, and revise finite automata, PDA and Turing machines in dependency order.
Non-Deterministic Finite Automata (NFA): Design, Epsilon Closures and NFA-to-DFA Conversion
Learn to follow every branch of an NFA without guesswork. Two worked machines connect active-state sets, epsilon closure and a complete eight-state DFA conversion.