GATE CSE Theory of Computation PYQs & Answers — Page 9

Questions 81–83 of 83. Imported answers require independent review unless marked reviewed.

Let δ denote the transition function and δ̂ denote the extended transition function of the ε-NFA whose transition table is given below:

δ	ε	a	b
→ q₀	{q₂}	{q₁}	{q₀}
q₁	{q₂}	{q₂}	{q₃}
q₂	{q₀}	∅	∅
q₃	∅	∅	{q₂}

Then δ̂(q₂, aba) is

Your answerChoose one option.

∅

{q₀, q₁, q₃}

{q₀, q₁, q₂}

{q₀, q₂, q₃}

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following languages:

L₁ = {aᵖ | p is a prime number} L₂ = {aⁿbᵐc²ᵐ | n ≥ 0, m ≥ 0} L₃ = {aⁿbⁿc²ⁿ | n ≥ 0} L₄ = {aⁿbⁿ | n ≥ 1}

Which of the following are CORRECT?

I. L₁ is context-free but not regular. II. L₂ is not context-free. III. L₃ is not context-free but recursive. IV. L₄ is deterministic context-free.

Your answerChoose one option.

I, II and IV only

II and III only

I and IV only

III and IV only

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?

I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ∅? III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ? IV. Given a Turing machine M and a string w, is w ∈ L(M)?

Your answerChoose one option.

I and IV only

II and III only

II, III and IV only

III and IV only

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE Theory of Computation PYQs

Question 39

Question 40

Question 41