GATE Solved Paper 2017-19 - GATE 2019

41. Which one of the following languages over Σ = {a, b}is NOT context-free?

  • Option : C
  • Explanation :
    (a) {wwR |w ∈ {a, b}* } is a CFL

    (b) {wan bn wR |w ∈ {a, b}*, n ≥ 0} is a CFL, since we can first push w, then a’s, b’s pop with a’s and wR pops with the w. So PDA can accept the language.

    (c) {wanwR bn|w ∈ {a, b}*, n ≥ 0} is a not CFL because after pushing w, we need to push a’s into stack which will stop the w from being matched with wR. If we don’t push a’s after w, than later we cannot match with bn. So this language is not acceptable by a PDA and hence not a CFL.

    (d) {anbi |i ∈ {n, 3n, 5n}, n ≥ 0} = anbn∪ anb3n∪ anb5n is CFL since each of the three parts is a CFL and closure under union guarantees that result also is a CFL.
Cancel reply
Cancel reply

42. Let the set of functional dependencies F = {QR → S, R → P, S → Q} hold on a relation schema X = (PQRS). X is not in BCNF. Suppose X is decomposed into two schemas Y and Z, where Y = (PR) and Z = (QRS). Consider the two statements given below.
I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is dependency preserving and lossless
Which of the above statements is/are correct?

  • Option : C
  • Explanation :
    X(PQRS) {QR → S, R → P, S → Q} decomposed into
     {R → P}{QR → S, S → Q}
     Candidate key : RCandidate key : QR, RS
     Relation Y in BCNFRelation Z in 3NF but not BCNF
    The common attribute between Y and Z relations is R which is key for relation Y.
    So that given decomposition is lossless join decomposition.
         R → P in Y
    and dependency preserving decomposition.
    Hence, C is the correct answer.
Cancel reply
Cancel reply

44. Consider the following sets:
S1Set of all recursively enumerable languages over the alphabet {0,1}
S2 Set of all syntactically valid C programs
S3 Set of all languages over the alphabet {0,1}
S4 Set of all non-regular languages over the alphabet {0,1}
Which of the above sets are uncountable?

  • Option : B
  • Explanation :
    S1: The set : LRE is known to be countably infinite since it corresponds with set of turing machines.
    S2: Since syntactically valid C programs surely run on Turing machines, this set is also : a subset of set of Turing machines, which is countable.
    S3: Set of all languages = 2Σ which is known to be uncountable. Σ* countably infinite
    ⇒ 2Σ is uncountable.
    S4: Set of all non-regular languages includes set : L NOT RE which is uncountable infinite and hence is uncountable.
    So, S3 and S4 are uncountable.
Cancel reply
Cancel reply

45. Consider the first order predicate formula 𝜑:
∀𝑥 [(∀𝑧 𝑧|𝑥⇒((𝑧=𝑥)∨(𝑧=1)))⇒∃𝑤 (𝑤>𝑥)∧(∀𝑧 𝑧|𝑤⇒((𝑤=𝑧)∨(𝑧=1)))]
Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following sets:
S1 {1,2,3,…,100}
S2 Set of all positive integers
S3 Set of all integers
Which of the above sets satisfy 𝜑?

  • Option : C
  • Explanation :
    ∀x[∀z⊗x ⇒ ((z = x) ∨ (z = 1)) ⇒ ∃w (w > x) ∧ (∀z z⊗w ⇒ ((w = z) ∨ (z = 1)))]

    The predicate ϕ simply says that if z is a prime number in the set then there exists another prime number is the set which is larger.

    Clearly ϕ is true in S2 and S3 since in set of all integers as well as all positive integers, there is a prime number greater than any given prime number.

    However, in S1 : {1, 2, 3, .....100} ϕ is false since for prime number 97 ∈ S1 there exists no prime number in the set which is greater. So correct answer is C.
Cancel reply
Cancel reply