GATE GATE Theory of Computation 1 ā Questions and Answers
Question 1: Which of the following languages is NOT regular?
- All strings over {a,b} with even length
- All strings over {a,b} starting with 'a'
- {a^n b^n | n ā„ 1} (Correct answer)
- All binary strings ending in '01'
Correct 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.
Question 2: What is the minimum number of states in a DFA that accepts all binary strings divisible by 3?
- 2
- 3 (Correct answer)
- 4
- 6
Correct 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.
Question 3: Which grammar type in the Chomsky hierarchy corresponds to context-free languages?
- Type 0
- Type 1
- Type 2 (Correct answer)
- Type 3
Correct 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.
Question 4: An NFA with n states can be converted to an equivalent DFA with at most how many states?
- n
- 2n
- nĀ²
- 2^n (Correct answer)
Correct 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.
Question 5: Which of the following problems is undecidable?
- Membership in a regular language
- Emptiness of a context-free language
- Equivalence of two Turing machines (Correct answer)
- Membership in a context-free language
Correct 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.
Question 6: Which of the following is true about a pushdown automaton (PDA)?
- PDAs can recognize all recursively enumerable languages
- PDAs are equivalent in power to context-free grammars (Correct answer)
- Deterministic PDAs recognize all context-free languages
- PDAs have two stacks
Correct 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.
GATE GATE Theory of Computation 1
Which of the following languages is NOT regular?