Time Left - 12:00 mins

Theory of Computation : Nuclear Quiz 2

Attempt now to get your rank among 298 students!

Question 1

Consider the following PDA state transition function

δ (q1,a,z0) = (q1,az0)

δ (q1,a,a) = (q1,aa)

δ (q1,b,a) = (q2,€)

δ (q2,b,a) = (q2,€)

δ (q2,c,a) = (q3,€)

δ (q3,c,a) = (q3,€)

δ (q3,€,z0) = (qf,z0)

where initial states ={q1}, states={q1,q2,q3,qf}, final state={qf} and stack alphabet={a,b,c,z0}.find the language satisfy by the above given state transition function.

Question 2

Consider the grammar G:
S aAε
A  aSbb
The language generated by G is ______

Question 3

Consider the following grammar.

Identify the language generated by above CFG?

Question 4

Consider the following statements:

S1 : Infinite union of regular languages can be context-free.

S2 : Language obtained after applying Kleen closure on a regular language will always be regular and infinite.
Which of the above statement is true?

Question 5

Which of the following is regular language?

Question 6

Which of the following languages is regular?
1) L= { (bba(ba)n a(n-1) | n>0 ) }
2) L= { (an bn) | n<1000 ) }
3) L= { (an bk) | n is odd or k is even) }
4) L= { (wxwr | w,x ( 0+1)^ * ) }

Question 7

Which of the following is CFL but not DCFL

Question 8

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

Question 9

Context free languages are closed under_______?

Question 10

For the following set of languages, which options holds true?

  • 298 attempts
  • 1 upvote