PREVIOUS YEAR SOLVED PAPERS - 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.
- Option : C
- Explanation : X(PQRS) {QR → S, R → P, S → Q} decomposed into
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 YY(PR) Z(QRS) {R → P} {QR → S, S → Q} Candidate key : R Candidate key : QR, RS Relation Y in BCNF Relation Z in 3NF but not BCNF 
and dependency preserving decomposition.
Hence, C is the correct answer.
- Option : B
- Explanation : 1 word = 4 bytes Page size = 8 kB = 213 B Number of words in 1 page = 213/22 = 211 TLB can hold 128 valid entries so, at most 128 × 211 memory address can be addressed without TLB miss. 128 × 211 = 256 × 210
- 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.
- 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.
