Time Left - 12:00 mins

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

Attempt now to get your rank among 849 students!

Question 1

Consider the following languages

1) L1={anbncm/n>m}

2) L2 = {xcy/x,y (0,1)*}

3) L3 = { aibjck /j=i+k}

4) L4= {w / w € (a,b) , na(w) >= nb(w)+1}

Number of languages that are Deterministic CFL ___.

Question 2

Consider recursively enumerable language (RE) and following operations

1) Intersection

2) Substitution

3) Union

4) Kleene closure

5) Complementation

6) Reversal

 The number of operations under which RE is closed ____.

Question 3

Consider the following grammar which is works on alphabet {a,b}.


Which of the following is the language that is generated by the above grammar?

Question 4

Which of the following relation is undecidable?

Question 5

What is the language generated by following unrestricted grammar

S-> S1B

S1-> aS1b

bB-> bbbB

aS1b ->aa

B-> €

Question 6

Which of the following is false?

Question 7

Minimum number of stacks required by PDA to behave like TM?

Question 8

consider the following statements

Statement 1- Set of all languages is uncountable, can be proved using diagonalization method.

Statement 2- Assume two languages A and B where A is reducible to B. If A is undecidable, B is undecidable.

Statement 3- if L is not RE then complement of L is also not RE.

Number of statements are correct is _____.

Question 9

Consider the CFG G(V,T,P,S) with the following production:

S -> AB|a

A -> a

Let CFG G’ is an equivalent CFG with no useless symbols. How many minimum production will be there in G’?

Question 10

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.

  • 849 attempts