Theory of Computation
17 articles in this topic
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.
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.
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.
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.
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.
Theory of Computation (TOC): Complete Guide with Worked Examples
Connect the main ideas of TOC through worked examples, from alphabets and DFA traces to grammars, stacks, Turing machines and decidability.
Regular Language Properties: Closure, Decision Tests, and Worked Examples
Connect closure properties, decision tests, and proof tools through product automata, pumping arguments, Myhill-Nerode reasoning, and checked string traces.
Grammar in Theory of Computation: Complete Guide with Worked Examples
Learn how grammars generate languages, classify all four Chomsky types, convert a regular grammar to an NFA, detect ambiguity, and use CNF step counts.
Chomsky Hierarchy for GATE: Classifying a Grammar as Regular, Context-Free, Context-Sensitive or Type-0
Classify grammars mechanically from their production forms. Four worked boundary cases show exactly when a grammar moves from regular to CFG, CSG or Type-0.
Rice's Theorem for GATE: The Mechanical Test for Undecidability Questions
Run the semantic and non-trivial checklist on six machine properties, learn when Rice is silent, and separate undecidable from RE or non-RE.
NFA to DFA Conversion for GATE: Subset Construction and State-Count Numericals
Convert two small NFAs into complete DFAs, handle epsilon-closure and the dead state, and separate the reachable state count from the 2^n worst case.