# CFL Closure Properties prove or disprove for the following languages

I have following statements which I must prove or disprove :

1) Let $L$ be a CFL and $k \in N$ then $L^k$ is also a CFL.
2) $L_1 \subseteq L_2 \subseteq L_3$ are Languages, if $L_1$ and $L_3$ are DCFL, then $L_2$ is also a DCFL

The first one I have no idea how to start or whether it is also a CFL

For the second one I think that this is false, because the CF contains the REG and DCF which means $L_2$ can be a REG-Language or a CFL or DCFL?

Is this right? at least this is how I understand it

• I think you should try harder. For part 1, use closure with respect to concatenation (if $L_1,L_2$ are context-free then so is $L_1L_2$). For part 2, consider $L_1 = \emptyset$ and $L_3 = \Sigma^*$. – Yuval Filmus Jul 3 '17 at 17:37
• if get this right, then i can use induction for the first part to prove that L^k is also CFL : for the second statements i still don't understand – proless8 Jul 3 '17 at 17:52
• Every language $L_2$ satisfies $\emptyset \subseteq L_2 \subseteq \Sigma^*$, the languages $\emptyset,\Sigma^*$ are both DCFL, but not all languages $L_2$ are context-free. – Yuval Filmus Jul 3 '17 at 18:08
• okay i understand the argument as a whole which makes sense but why is $\Sigma^*$ DCFL ? – proless8 Jul 3 '17 at 18:16
• It's a regular language and so DCFL. – Yuval Filmus Jul 3 '17 at 18:16

1) Since the context-free languages are closed under concatenation, a simple induction shows that if $L$ is context-free then so is $L^k$, for all $k \geq 0$.
2) Let $L_2$ be a language over an alphabet $\Sigma$ which is not context-free. Then $\emptyset \subseteq L_2 \subseteq \Sigma^*$, refuting the statement (since $\emptyset$ and $\Sigma^*$ are regular and so deterministic context-free).
1) If $L$ is a CFG then assume $S$ is the start symbol of the grammar rules. Then introduce a new start symbol $S' \rightarrow SS\dots SS$ ($k$ times). So if $w \in L^k$ then $w$ can be written as $u_1u_2\dots u_k$ where $S \Rightarrow^* u_1$, $\dots$, $S \Rightarrow^* u_k$ and so $S' \rightarrow SS\dots S \Rightarrow^* u_1u_2\dots u_k$. Now suppose that $S' \Rightarrow w$. Then since $S' \Rightarrow SS\dots S \Rightarrow^* w$, $w$ clearly in $L^k$. Thus, $L^k$ is CF.
2) $L_1 = \{ 0^i | i \in N\}$, $L_2 = \{ 0^i1^j2^k | i,j,k \in N, i=j \ or \ j=k\}$, $L_3 = \{ 0^i1^j2^k | i,j,k \in N\}$. Clearly $L_1 \subset L_2 \subset L_3$. But $L_2$ is not CFL, so not DCFL.