PREVIOUS YEAR SOLVED PAPERS - GATE 2017 Shift 2

Avatto > > GATE COMPUTER SCIENCE > > PREVIOUS YEAR SOLVED PAPERS > > GATE 2017 Shift 2

61. 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)?

Answer
Comment
Array

Option : D
Explanation :
Is the language represented by regular expression
L(G) is the language generated by context free grammar
L(M) is the language accepted by Turing Machine

I. The problem a given regular expression R and a string w, is is a membership problem. Membership problem is decidable for Finite state machine and regular expression.

II. Given Context free grammar G, is L(G) is ϕ?, is emptiness problem for context free grammar. Emptiness problem is decidable for CFG by checking usefulness of start symbol.

III. A given context free grammar G, is L(G) is Σ* for some alphabet Σ?, is undecidable problem. We can’t check whether L(G) = Σ* or not but rather we can check complement of L(G) is ϕ. Since context free language are not closed under complement operation L(G) may be language accepted by Turing Machine and we can’t check emptiness for Turing machine.

IV. Given a Turing Machine M and a string w, is w Î L(M)?, is a membership problem for TM. Membership problem is not a decidable problem for TM.

62. Consider a machine with a byte addressable main memory of 2³² bytes divided into blocks of size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with this machine. The size of the tag field in bits is ______.

Note – Numerical Type question

Answer
Comment
Array

Option : A
Explanation :
Number of blocks of main memory = 2³² / 2⁵ = 2²⁷
Number of blocks in cache memory = 512 = 2⁹
1 Cache block points to 2²⁷ / 2⁹ = 2¹⁸ lines
So, Number of TAG bits required = 18 bits.

63. Let δ denote the transition function and δˆ denote the extended transition function of the ϵ-NFA whose transition table is given below:

Then δˆ(q₂,aba) is

Answer
Comment
Array

Option : C
Explanation :
The given table for NFA-ϵ Transition is

The process is we start with ϵ-closure of q₂ then for each input first take the transition then calculate ϵ-closure
q₂ is the start for processing we take ϵ-closure which is {q₀, q₂ and process “aba”
q₂ can reach q0, q1, and q2 after reading “aba”.

64. Consider the following languages.
L₁ = {a^p | p is a prime number}
L₂ = {aⁿb^mc^2m | 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.

Answer
Comment
Array

Option : D
Explanation :
L₁ is neither regular nor context free but context sensitive language.
L₂ is context free, push any number of a’s and then for each b, pop two c’s until all b’s are over and this can be done by using only one stack.
L₃ is not context free because we are not sure when to pop b and push a, because it is comparison between three consecutive terminals.
Clearly L₃ is deterministic context free because we are sure of pushing a into stack first and on seeing b we are sure of popping a.
Statement III and IV are correct, option (D) is true.

Related Quiz.
GATE 2017 Shift 2

Forgot your password?

I agree with the Terms.