GATE CSE: Theory of computation

Question 1 of 10

The language { aⁿbⁿ | n ≥ 0 } is:

Question 2 of 10

The language { aⁿbⁿcⁿ | n ≥ 0 } is:

Question 3 of 10

How many states does the minimal DFA have for binary numbers (read most significant bit first) divisible by 3?

Question 4 of 10

Which class is NOT closed under complementation?

Question 5 of 10

The halting problem for Turing machines is:

Question 6 of 10

The regular expression (0+1)*1(0+1)(0+1) describes binary strings where:

Question 7 of 10

Subset construction turns an NFA with n states into a DFA with at most:

Question 8 of 10

The pumping lemma for regular languages is used to show a language is:

Question 9 of 10

Whether a string is generated by a context-free grammar in Chomsky normal form can be decided by:

Question 10 of 10

Context-free languages are exactly the languages accepted by: