1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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^*$. $\endgroup$ – Yuval Filmus Jul 3 '17 at 17:37
  • $\begingroup$ 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 $\endgroup$ – proless8 Jul 3 '17 at 17:52
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 3 '17 at 18:08
  • $\begingroup$ okay i understand the argument as a whole which makes sense but why is $\Sigma^*$ DCFL ? $\endgroup$ – proless8 Jul 3 '17 at 18:16
  • $\begingroup$ It's a regular language and so DCFL. $\endgroup$ – Yuval Filmus Jul 3 '17 at 18:16
0
$\begingroup$

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).

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ thank you very much, although it's a bit complicated to understand the prove but i get it now $\endgroup$ – proless8 Jul 3 '17 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.