Theory of Computation in GATE rewards precise thinking: knowing exactly which language class a language belongs to, which closure properties hold, and which problems are decidable. This GATE-style set covers each level of the Chomsky hierarchy with short, exam-focused explanations.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 15 questions.
Topics covered in this set
- Regular expressions and minimal DFA
- NFA to DFA conversion
- Pumping lemma and non-regular languages
- Context-free languages, PDAs and DCFLs
- Closure properties
- Decidability and the halting problem
GATE CSE Theory of Computation MCQs with answers and explanations
Q1. Which strings does the regular expression (a+b)*abb describe?
a) All strings over {a, b} that end with abb
b) Strings that start with abb
c) Strings containing exactly one abb
d) Strings of length 3 only
Q2. How many states does the minimal DFA have for binary strings in which the number of 0s is divisible by 3?
a) 6
b) 2
c) 4
d) 3
Q3. How many states does the minimal DFA have for binary strings that end with "01"?
a) 3
b) 2
c) 5
d) 4
Q4. Which language is NOT regular?
a) {aⁿbⁿ | n ≥ 0}
b) {aⁿ | n is even}
c) Strings over {a, b} with an even number of a's
d) Strings ending in ab
Q5. The language {aⁿbⁿcⁿ | n ≥ 1} is:
a) Context-free but not regular
b) Not recursively enumerable
c) Context-sensitive but not context-free
d) Regular
Q6. Context-free languages are NOT closed under which operation?
a) Intersection
b) Concatenation
c) Union
d) Kleene star
Q7. In the worst case, how many states can the DFA obtained by subset construction from an NFA with n states have?
a) 2ⁿ
b) n!
c) n
d) n²
Q8. Which of these languages is deterministic context-free?
a) {aⁿbⁿcⁿ}
b) {ww^R | w ∈ {a, b}*}
c) {wcw^R | w ∈ {a, b}*}
d) {ww | w ∈ {a, b}*}
Q9. Regular languages are closed under:
a) None of these operations
b) Union and concatenation, but not complement
c) Complement, union, intersection, concatenation and Kleene star
d) Union only
Q10. Which problem is decidable?
a) Whether a context-free grammar is ambiguous
b) Whether a Turing machine halts on a given input
c) Whether two context-free grammars generate the same language
d) Whether a given string is generated by a given context-free grammar
Q11. The language of the halting problem, {⟨M, w⟩ | M halts on w}, is:
a) Recursively enumerable but not recursive
b) Regular
c) Not recursively enumerable
d) Recursive (decidable)
Q12. A Turing machine that halts on every input and accepts exactly the strings of L shows that L is:
a) Recursively enumerable only
b) Context-free
c) Recursive (decidable)
d) Regular
Q13. The pumping lemma for regular languages is mainly used to:
a) Minimise a DFA
b) Prove a language is not regular
c) Prove a language is regular
d) Convert an NFA to a DFA
Q14. How many strings of length 3 over {a, b} match the regular expression a(a+b)*?
a) 8
b) 3
c) 4
d) 6
Q15. If L is recursively enumerable and its complement is also recursively enumerable, then L is:
a) Context-free
b) Recursive
c) Regular
d) Undecidable
Quick revision notes
- Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE.
- CFLs: closed under union, concatenation, star; not under intersection or complement.
- Subset construction can need 2ⁿ DFA states.
- CFG membership is decidable; CFG equivalence and ambiguity are not.
- L and its complement both RE implies L is recursive.
Frequently asked questions
Are these GATE previous year questions?
No, they are original GATE-style questions covering commonly tested concepts.
What is the fastest way to classify a language?
Ask what memory is needed: a fixed finite amount means regular, one stack means context-free, and comparing three or more unbounded counts usually means context-sensitive.
Is the complement of a CFL always a CFL?
No. The complement of a deterministic CFL is a DCFL, but for general CFLs it may not be context-free.
Comments
Post a Comment