Last Minute Notes Theory of Computation
With limited time before the exam, your goal is to consolidate the most frequently tested facts and techniques in Theory of Computation into a form you can...
Quick Revision: Finite Automata and Regular Languages
With limited time before the exam, your goal is to consolidate the most frequently tested facts and techniques in Theory of Computation into a form you can quickly recall. This section covers Finite Automata and Regular Languages, which alone account for roughly half the marks GATE allocates to TOC.
A DFA accepts a string if and only if processing all its symbols leads to an accepting state. An NFA accepts if at least one computation path leads to acceptance. Every NFA has an equivalent DFA via subset construction. Every regular language has a unique minimal DFA. Use the table-filling algorithm to minimize: mark distinguishable pairs, propagate, merge unmarked pairs.
Regular expressions and finite automata are equivalent descriptors of regular languages. Key regex operators are concatenation, union represented by the pipe symbol, and Kleene star. Converting between regex and automata uses Thompson's construction for regex to NFA and state elimination for DFA to regex.
Closure properties to remember: regular languages are closed under union, intersection, complement, concatenation, Kleene star, reversal, homomorphism, and inverse homomorphism. They are not closed under operations that can create context-free structure.
The pumping lemma pumping length is the key: if a string is at least as long as p, it can be pumped. The y segment chosen must be within the first p characters and must be nonempty. Remember that the pumping lemma gives a necessary condition, not a sufficient one, so you cannot use it to prove a language is regular.
Important decision algorithms for regular languages: membership, emptiness, finiteness, equivalence, and inclusion are all decidable. The minimal DFA for a regular language is unique up to state relabeling, which means two DFAs accept the same language if and only if their minimal forms are isomorphic.
For last-minute practice, sketch the minimal DFA for common languages: strings ending in 01, strings containing 101 as a substring, strings with even number of 0s. Time yourself and aim to complete each in under three minutes. Verify by testing a few strings mentally. These small exercises sharpen the pattern recognition you need on exam day.
Quick Revision: Pushdown Automata and Context-Free Grammars
Context-Free Grammars and Pushdown Automata are the second pillar of TOC revision. These concepts are tested in GATE through grammar design, language identification, and ambiguity questions. Here is a compressed review of the essential facts.
A context-free grammar has productions of the form A goes to alpha, where A is a nonterminal and alpha is any string of terminals and nonterminals. A derivation is a sequence of production applications starting from the start symbol. A parse tree represents a derivation graphically. Ambiguity means at least two distinct parse trees exist for some string. Inherent ambiguity means every grammar for that language is ambiguous. The standard example of an inherently ambiguous language involves mixing two different structural patterns that cannot be separated.
Grammar simplification steps in order: first remove null productions except for the start symbol if the empty string is in the language, then remove unit productions which are rules of the form A goes to B, then remove useless symbols which are either unreachable from the start or unable to derive any terminal string. Converting to Chomsky Normal Form means every rule is either A goes to BC or A goes to a. Converting to Greibach Normal Form means every rule starts with a terminal.
A Pushdown Automaton accepts either by final state or by empty stack, and both models are equivalent in power. Given a context-free grammar, you can construct an equivalent PDA that simulates leftmost derivations using the stack. Deterministic PDAs are strictly less powerful than nondeterministic PDAs.
Closure properties: context-free languages are closed under union, concatenation, and Kleene star. They are not closed under intersection or complement. The intersection of a context-free language with a regular language is always context-free, which is a commonly tested fact.
For the exam: if a GATE question gives you a grammar and asks whether it is ambiguous, try to find two different parse trees for a short string. If it asks for the language of a grammar, derive a few strings and look for the pattern. If it asks you to build a grammar, think about what structural constraint defines the language and model it with a recursive rule.
Quick Revision: Turing Machines and Decidability Facts
The final cluster of TOC topics for last-minute revision covers Turing Machines, decidability, and complexity. These are the most conceptual parts of the subject, and GATE tests them through classification questions rather than construction tasks.
A Turing Machine configuration is described by the current state, the current tape contents, and the head position. The machine halts when it enters a halt state. A language is recursive, also called decidable, if there is a Turing Machine that accepts all strings in the language and rejects all strings not in it, always halting. A language is recursively enumerable if there is a Turing Machine that accepts all strings in the language but may loop forever on strings outside it.
Every recursive language is also recursively enumerable. The complement of a recursive language is recursive. If a language and its complement are both recursively enumerable, then both are recursive. These relationships form a lattice that is commonly tested.
Decidable problems include: does a DFA accept a given string, is a DFA's language empty, do two DFAs accept the same language, does a given context-free grammar generate a given string. Undecidable problems include: the Halting Problem, whether a Turing Machine accepts any string at all, whether two Turing Machines recognize the same language, and by Rice's Theorem, any non-trivial semantic property of Turing Machine languages.
Reductions are how we show undecidability. If problem A reduces to problem B, and A is undecidable, then B is also undecidable. The key is the direction of the reduction arrow: A reduces to B means solving B would let you solve A.
Rice's Theorem states: any non-trivial property of the language recognized by a Turing Machine is undecidable. Non-trivial means some TMs have it and some do not. Properties about languages, not machines, are what this covers. Whether a TM has an even number of states is a property of the machine, not the language, and Rice's Theorem does not apply to it.
Remember: in GATE, when you see a question about whether some property of TMs or their languages is decidable, your first instinct should be to check Rice's Theorem applicability.