Examius
🇮🇳 GATE CS & IT Engineering · flashcards
GATE CS & IT Engineering Theory of Computation Flashcards
50 question-and-answer cards covering Theory of Computation as it is examined in GATE CS & IT Engineering. 24 of them are printed below, taken from across the deck — no signup, no paywall on the preview.
24 sample cards from the Theory of Computation deck
Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.
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.).
What this deck covers
The Theory of Computation deck follows the GATE CS & IT Engineering Theory of Computation syllabus — 4 chapters and 9 topics — so questions land on material that is genuinely examinable rather than trivia around it. That works out to roughly 12.5 cards per chapter.
Answers are written to be recallable, not just readable — averaging about 178 characters, which is long enough to carry the reasoning and short enough to say out loud.
A deck like this earns its keep on the second and third pass. Read the syllabus first so you know the shape of the subject, then use the cards to find the specific facts that have not stuck.
Theory of Computation flashcards FAQ
How many Theory of Computation flashcards are in this GATE CS & IT Engineering deck?
50 cards. This page previews 24 of them, sampled evenly across the deck so you can judge the difficulty before installing anything.
Are these GATE CS & IT Engineering flashcards free?
Yes. The preview here is free to read with no signup, and the full 50-card deck is free inside the Examius app.
What do the Theory of Computation cards cover?
They follow the GATE CS & IT Engineering Theory of Computation syllabus — 4 chapters and 9 topics — so the questions track what is actually examinable.
How should I use these flashcards?
Read the syllabus first so you know the shape of the subject, then drill the deck. Examius schedules each card with spaced repetition, so cards you keep missing come back sooner and ones you know drift further apart.