Time Left - 12:00 mins

BARC 2020: Theory Of Computation Nuclear Quiz 1 (App update required to attempt this test)

Attempt now to get your rank among 590 students!

Question 1

The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is _________. a*b* (ba)* a*

Question 2

Consider the following ε-NFA

The number of final states in DFA is?

Question 3

Time complexity of CYK algorithms where |w| is length of the strings?

Question 4

Context free grammar is not closed under?

Question 5

How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?

Question 6

Number of productions remain after removal of -productions for the CFG


A aAA|

B bBB |

Question 7

Minimum number of states will be there in state diagram of context free language acceptance by final state is-

L={w / na(w)=nb(w)}

Question 8

Which of the following machine is more powerful in terms of language what they can represent?

Question 9

Context free grammar refers to the following type of automata strictly

Question 10

Consider the following statements:

Statement 1- Since the Post correspondence problem is undecidable that is why ambiguity problem is also undecidable.

Statement 2-For context-free grammar(CFG) G1, it is undecidable whether L(G1) is regular.

Statement 3- For two CFG, G1 and G2, the intersection of L(G1) and L(G2) is empty or not is decidable.

Number of False statement/statements are ____.

  • 590 attempts
  • 1 upvote