UGC NET Computer Science December 2019 | Question 97

Question 97

---

Consider the following statements with respect to the language L = {aⁿbⁿ | n >= o}
S1: L² is context free language
S2: L^k is conext-free language for any given k >= 1
S3: L' and L* are context free languages
Which one of the following is correct?

1. (1) only S1 and S2
2. (2) only S1 and S3
3. (3) only S2 and S3
4. (4) S1, S2, and S3

Answer : (4) S1, S2, and S3

Explanation

S1 is correct because L² means L.L i.e resulting language will be L² = {aⁿbⁿaⁿbⁿ | n ≥ 0 which is a context free language.

Since context free languages are closed under kleen closure so L^k is context-free language for any given k ≥ 1. Hence S2 is correct.

Complement of given language L will be a language accepting all strings other than {aⁿbⁿ | n ≥ 0}. And we can easily design a pushdown automata which rejects {aⁿbⁿ | n ≥ 0} and accepts all string other than this. And as we know, context free languages are closed under kleen closure. Hence S3 is correct.

So, option 4 is correct answer

Previous	Next
UGC NET CS December 2019 - Question 96	UGC NET CS December 2019 - Question 98