Theory of Computation
47 articles in this topic
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.
Updated 29 Aug 20266 min readTheory of Computation
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.
Updated 27 Aug 20266 min readTheory of Computation
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.
Updated 26 Aug 20265 min read521 viewsTheory of Computation
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.
Updated 24 Aug 20266 min readTheory of Computation
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.
Updated 22 Aug 20265 min readTheory of Computation
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.
Updated 21 Aug 20266 min readTheory of Computation
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.
Updated 19 Aug 20265 min read51 viewsTheory of Computation
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.
Updated 17 Aug 20266 min read58 viewsTheory of Computation
Regular Expressions in Theory of Computation: Rules, Conversions and Worked Examples
Learn what classical regular expressions denote, construct one from a language condition, convert it through NFA and DFA, and check equivalence with worked examples.
Updated 15 Aug 20266 min read105 viewsTheory of Computation
Moore and Mealy Machines: Output Tracing, Conversion and Worked Examples
Learn how state outputs and transition outputs change a trace. Two binary examples show parity, Moore-to-Mealy conversion and the exact state splitting needed in the reverse direction.
Updated 13 Aug 20266 min readTheory of Computation
Deterministic Finite Automata (DFA): Design, Tracing and Minimisation with Worked Examples
Learn a repeatable way to design DFA states, trace binary inputs, build complements and products, and minimise a complete machine. Every transition is checked through exact tables and worked traces.
Updated 10 Aug 20266 min readTheory of Computation
Turing Machines in Theory of Computation: Design, Worked Trace and Decidability
A six-state Turing machine for L = {0^n1^n}: built from the seven-tuple, traced move by move on 0011 to XXYY and q_accept, then proved a decider rather than only a recogniser.
Updated 8 Aug 20266 min read70 viewsTheory of Computation