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

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

2 Answers 2

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

$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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