GATE Theory of Computation Flashcards
6 cards from real GATE practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 GATE Theory of Computation flashcards as text
Which of the following languages is NOT regular?
Answer: {a^n b^n | n ≥ 1}
The language {a^n b^n} requires counting and matching equal numbers of a's and b's, which exceeds the capability of finite automata.
What is the minimum number of states in a DFA that accepts all binary strings divisible by 3?
Answer: 3
A DFA with 3 states (representing remainders 0, 1, 2 when divided by 3) is sufficient to accept all binary strings divisible by 3.
Which grammar type in the Chomsky hierarchy corresponds to context-free languages?
Answer: Type 2
Type 2 (context-free) grammars have productions of the form A → α, where A is a single non-terminal and α is any string of terminals and non-terminals.
An NFA with n states can be converted to an equivalent DFA with at most how many states?
Answer: 2^n
The subset construction algorithm for NFA-to-DFA conversion can produce up to 2^n states, one for each subset of the NFA's n states.
Which of the following problems is undecidable?
Answer: Equivalence of two Turing machines
The equivalence problem for Turing machines is undecidable; no algorithm can determine whether two arbitrary Turing machines accept the same language.
Which of the following is true about a pushdown automaton (PDA)?
Answer: PDAs are equivalent in power to context-free grammars
Pushdown automata (nondeterministic) are exactly equivalent to context-free grammars — both define the class of context-free languages.