UGC NET CSE | December 2019 | Part 2 | Question: 47

Question

Consider the following statements with respect to the language $L = \{ a^n b^n \mid n \geq 0 \}$

$S_1 : L^2$ is a context free language

$S_2 : L^k$ is context free language for any given $k \geq 1$

$S_3 :  \overline{L}$ and $L^\ast$ are context free languages

Which one of the following is correct?

• A. only $S_1$ and $S_2$
• B. only $S_1$ and $S_3$
• C. only $S_2$ and $S_3$
• D. $S_1$, $S_2$ and $S_3$

Answer 1

Regular Grammar is Closed under Union, Intersection, Kleen Closure and complement. Context free grammar is closed under Union and Kleen Closure.

This L being a regular grammar it’s closed under all 4. Hence all three statements are correct.

(A regular grammar will always be context free)

Hence option D.

Comments

Which grammar are you talking about?

---

Here L is a Context free grammar.

---

Yea. You are right. My mistake.

Answer 2

L={anbn∣n≥0}L={anbn∣n≥0}

The given Language is Context free language and CFL are closed under Union, Concatenation, and kleen closure,

S1 :  $L^2$ is a context free language, here  $L^2$ can be writtern as

$L^2$ = L.L and CSL is closed under concatenation so  $L^2$ is a CFL

 

S2:$L^k$ context free language for any given k≥1, $L^k$ can be writtern as L.L.L…..k times and CFL are closed under concatenation so $L^k$ is CFL

S3: L¯  and  $L^∗$ are context free languages

Context free language are not closed under complementation for complement of L may be CFL or CSL.

here complement of L is CFL,

and CFL are closed under kleen closure (*) so it is CFL.

so correct ans is D.