GATE Solved Paper 2017-19 - 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)?

  • 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.
Cancel reply
Cancel reply

62. Consider a machine with a byte addressable main memory of 232 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 ______.

  • Option : A
  • Explanation :
    Number of blocks of main memory = 232 / 25 = 227
    Number of blocks in cache memory = 512 = 29
    1 Cache block points to 227 / 29 = 218 lines
    So, Number of TAG bits required = 18 bits.
Cancel reply
Cancel reply

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

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

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

64. Consider the following languages.
L1 = {ap | p is a prime number}
L2 = {anbmc2m | n >= 0, m >= 0}
L3 = {anbnc2n | n >= 0}
L4 = {anbn | n >= 1}

Which of the following are CORRECT ?
I. L1 is context free but not regular.
II. L2 is not context free.
III. L3 is not context free but recursive.
IV. L4 is deterministic context free.

  • Option : D
  • Explanation :
    L1 is neither regular nor context free but context sensitive language.
    L2 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.
    L3 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 L3 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.
Cancel reply
Cancel reply