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

- Option : C
- Explanation :

(a) {ww^{R}|w ∈ {a, b}* } is a CFL

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

(c) {wa^{n}w^{R}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 w^{R}. 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) {a^{n}b^{i}|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.

You must be logged in to post a comment.

- 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.Y(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

So that given decomposition is lossless join decomposition.

R → P in Y

and dependency preserving decomposition.

Hence, C is the correct answer.

You must be logged in to post a comment.

You must be logged in to post a comment.

- Option : B
- Explanation :

S_{1}: The set : L_{RE}is known to be countably infinite since it corresponds with set of turing machines.

S_{2}: Since syntactically valid C programs surely run on Turing machines, this set is also : a subset of set of Turing machines, which is countable.

S_{3}: Set of all languages = 2^{Σ}which is known to be uncountable. Σ* countably infinite

⇒ 2^{Σ}is uncountable.

S_{4}: Set of all non-regular languages includes set : L_{ NOT RE}which is uncountable infinite and hence is uncountable.

So, S_{3}and S_{4}are uncountable.

You must be logged in to post a comment.

You must be logged in to post a comment.

- 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 S_{2}and S_{3}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 S_{1}: {1, 2, 3, .....100} ϕ is false since for prime number 97 ∈ S_{1}there exists no prime number in the set which is greater. So correct answer is C.

You must be logged in to post a comment.

You must be logged in to post a comment.

You must be logged in to post a comment.