GATE CS & IT Engineering Theory of Computation Syllabus

Define a pushdown automaton (PDA) as a 7-tuple.

A PDA is $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ where $Q$ states, $\Sigma$ input alphabet, $\Gamma$ stack alphabet, $\delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \to 2^{Q \times \Gamma^{*}}$, $q_0$ start state, $Z_0$ initial stack symbol, $F$ accepting states.

Are nondeterministic PDAs and deterministic PDAs equivalent in power?

No. Nondeterministic PDAs recognize exactly the context-free languages, while deterministic PDAs (DPDAs) recognize only a proper subset, the deterministic context-free languages.

What is the relationship between PDAs and context-free grammars?

A language is context-free if and only if it is accepted by some (nondeterministic) pushdown automaton; CFGs and PDAs have equivalent expressive power.

What are the two equivalent acceptance criteria for a PDA?

Acceptance by final state and acceptance by empty stack. For nondeterministic PDAs these define the same class of languages (the CFLs).

State the pumping lemma for context-free languages.

For every CFL $L$ there is a constant $p$ such that any $z \in L$ with $|z| \geq p$ can be written $z = uvwxy$ with $|vwx| \leq p$, $|vx| \geq 1$, and $uv^{i}wx^{i}y \in L$ for all $i \geq 0$.

Use the CFL pumping lemma idea to show $\{a^{n}b^{n}c^{n} : n \geq 0\}$ is not context-free.

For $z = a^{p}b^{p}c^{p}$, the substring $vwx$ spans at most two of the three symbol types; pumping changes the counts of at most two symbols, breaking equality of all three counts, so $uv^{2}wx^{2}y \notin L$.

Which closure operations are context-free languages closed under?

CFLs are closed under union, concatenation, Kleene star, reversal, and homomorphism.

Which closure operations are context-free languages NOT closed under?

CFLs are not closed under intersection or complementation. (However, the intersection of a CFL with a regular language is context-free.)

Is the intersection of a context-free language and a regular language context-free?

Yes. The class of CFLs is closed under intersection with regular languages, even though it is not closed under intersection with arbitrary CFLs.

Define a (deterministic) Turing machine as a 7-tuple.

A TM is $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$ where $\Gamma \supseteq \Sigma$ is the tape alphabet (including blank), and $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ specifies the next state, symbol written, and head move.

What is the difference between a recursive (decidable) language and a recursively enumerable (recognizable) language?

A recursive language is decided by a TM that halts on all inputs (accept or reject). A recursively enumerable language is recognized by a TM that halts and accepts on members but may loop forever on non-members.

State the relationship between a language $L$ being recursive and both $L$ and its complement being recursively enumerable.

$L$ is recursive (decidable) if and only if both $L$ and its complement $\overline{L}$ are recursively enumerable.

Is the class of recursive (decidable) languages closed under complement?

Yes. Recursive languages are closed under complement (swap accept and reject states). Recursively enumerable languages are NOT closed under complement.

What is the Church-Turing thesis?

Any function that is effectively computable by an algorithm (any mechanical procedure) can be computed by a Turing machine; the TM captures the intuitive notion of effective computability.

State the halting problem and its decidability status.

The halting problem asks, given a TM $M$ and input $w$, whether $M$ halts on $w$. It is undecidable: no TM can decide $H = \{\langle M, w\rangle : M \text{ halts on } w\}$ for all inputs.

Is the halting problem recursively enumerable?

Yes, the halting problem is recursively enumerable (semi-decidable) — a universal TM can simulate $M$ on $w$ and accept if it halts — but it is not recursive (decidable).

State Rice's theorem.

Every non-trivial semantic property of the language recognized by a Turing machine is undecidable. A property is non-trivial if some TMs have it and some do not, and it depends only on the language (not the machine's encoding).

What is the standard technique for proving a problem undecidable?

Reduction: show that a known undecidable problem (e.g. the halting problem $A_{TM}$) reduces to the target problem, so a decider for the target would yield a decider for the known undecidable problem — a contradiction.

Give the membership-problem decidability status for regular and context-free languages.

Membership is decidable for both: for regular languages run the DFA on the string; for CFLs use the CYK algorithm in $O(n^{3})$ time on a CNF grammar.

Which decision problems are decidable for regular languages but undecidable for context-free languages?

Equivalence ($L_1 = L_2$), and emptiness of the complement/universality ($L = \Sigma^{*}$) are decidable for regular languages but undecidable for CFLs. Also CFL ambiguity and CFL containment are undecidable.

Are emptiness and finiteness decidable for context-free languages?

Yes. Both emptiness ($L = \emptyset$) and finiteness of a CFL are decidable, e.g. by examining which variables are generating and reachable in the grammar.

What is the time complexity of the CYK parsing algorithm and what grammar form does it require?

$O(n^{3})$ time for a string of length $n$ (with the grammar size as an additional factor); it requires the grammar in Chomsky Normal Form.

What is a leftmost derivation in a CFG?

A derivation in which, at each step, the leftmost non-terminal in the current sentential form is the one replaced by a production.

What is the language recognized by a finite automaton called, and give one example that is NOT in this class.

A regular language. An example outside the class (not regular) is $\{a^{n}b^{n} : n \geq 0\}$, which requires unbounded counting that a finite automaton cannot do.

What is the Post Correspondence Problem (PCP) and its decidability status?

Given two lists of strings $(x_1,\dots,x_n)$ and $(y_1,\dots,y_n)$, PCP asks whether there is a sequence of indices $i_1\dots i_k$ with $x_{i_1}\cdots x_{i_k} = y_{i_1}\cdots y_{i_k}$. PCP is undecidable.

How do you convert a regular expression to an NFA, and how many states does Thompson's construction add per operator?

By Thompson's construction, building NFA fragments recursively for base symbols and combining them with $\epsilon$-transitions for union, concatenation, and star. Each operator adds a constant number of states, giving an NFA linear in the regex size.

What property must hold of a DFA's transition function that need not hold for an NFA?

A DFA must be total and deterministic: exactly one transition is defined for every (state, input symbol) pair, with no $\epsilon$-moves. An NFA may have zero, one, or many transitions, plus $\epsilon$-moves.

Compare the memory models of finite automata, pushdown automata, and Turing machines.

A finite automaton has only finite-state memory (no auxiliary storage); a PDA adds a single unbounded LIFO stack; a Turing machine has an unbounded read/write tape with two-way head movement, the most powerful of the three.

Is the equivalence problem for two DFAs decidable?

Yes. Equivalence of DFAs (and of regular expressions/NFAs) is decidable — e.g. by minimizing both DFAs and checking isomorphism, or testing whether the symmetric difference language is empty.

State whether the union, intersection, and complement of two recursively enumerable languages are recursively enumerable.

Recursively enumerable languages are closed under union and intersection, but NOT under complement (the complement of an r.e. but non-recursive language is not r.e.).