Time Left - 15:00 mins

GATE CS 2021 : Theory of computation Quiz 8 (App update required to attempt this test)

Attempt now to get your rank among 684 students!

Question 1

Which one of the following problems is undecidable?

Question 2

which of the following is decidable problem for Context free languages

Question 3

Pumping lemma is generally used for proving :

Question 4

Which of the following relation is undecidable?

Question 5

How many of the following statements are true?

1) The intersection of two regular languages is infinite is decidable.

2) Whether a given context free language is regular is decidable.

3) Whether a given grammar is context free grammar is not decidable.

4) Finiteness problem of regular language is decidable.

Question 6

How many of the following problem are decidable?

A) Does a given program ever produce an output.

B) If L is CFL, Then L’ is also CFL.

C) Given a CFG, G , L(G) = {empty}.

D) If L is a recursive language, then , is L’ also recursive.

  • 684 attempts
  • 6 upvotes
  • 10 comments
Apr 12GATE & PSU CS