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

Consider the following languages

1) L1={aⁿbⁿc^m/n>m}

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

3) L3 = { aⁱb^jc^k /j=i+k}

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

Number of languages that are Deterministic CFL ___.

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

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

S->aSa/bSb/a/€

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

Which of the following relation is undecidable?

What is the language generated by following unrestricted grammar

S-> S₁B

S₁-> aS₁b

bB-> bbbB

aS₁b ->aa

B-> €

Which of the following is false?

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

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

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’?

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.