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

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

Consider the following ε-NFA

The number of final states in DFA is?

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

Context free grammar is not closed under?

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

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

S→ AB

A→ aAA|€

B→ bBB |€

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

L={w / n_a(w)=n_b(w)}

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

Context free grammar refers to the following type of automata strictly

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 ____.