Time Left - 15:00 mins

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

Attempt now to get your rank among 551 students!

Question 1

Consider the following statements regarding to the pumping lemma-
I. If NFA accept a string of length having atleast equal to the number of states I.e |w|<=n then language is infinite.
II. If n state FA is accepting infinite language it surely accept the string between length n & 2n-1.
Then which of the following is true regarding it?

Question 2

Consider the following statements:

S1 : {(an)m |n < m > 0}

S2 :{(anbn)|n >1} {anbm |n>1, m > 1}

Which of the following is regular?

Question 3

The language of primes in unary is:

Question 4

Whether the language given by L = {anb2nc3n | n>=1} is CFL or not? Write 1 for true or 0 for false.

Question 5

Which one of the following languages over Σ = {a, b}is NOT context-free?

Question 6

Consider the following sentences.

I. If L1 L2 is regular, then both L1 and L2 must be regular.

II. The class of regular languages is closed under infinite union.

Which of the above statements is/are TRUE?

  • 551 attempts
  • 3 upvotes
  • 2 comments
Oct 5GATE & PSU CS

Posted by:

Harshita AgarwalHarshita AgarwalMember since Jul 2020
Share this quiz   |