2
$\begingroup$

I was reviewing the post If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?

I completely understand why $L/R$ is context free.

I just tried a different approach, which is not that rigorous according to the answers given. It is just based on the basic understanding.

How I tried :

Let $L = a^N b^N a^M b^M$ and $R = \left (a + b \right )^*$.

Then $wx$ belongs to $L$. Suppose I assume $wx = aaabbbab$.

So, now $x = ab$ which belongs to $R$.

So $L/R$ contains $aaabbb$.

Like this, I will get all strings in $L/R = \left \{ a^N b^N | N \geq 1 \right \}$.

This language is nothing but context free.

This approach is not as rigorous as what I saw in the answers.

I just want to confirm: is this approach right?

$\endgroup$
6
$\begingroup$

You can't prove a general theorem by proving one special case. So even if your proof of the special case were correct (and it isn't), all it does is prove that the theorem holds in that specific case.

Your proof is erroneous since $L/R$ is larger than what you indicate. In fact, whenever $\epsilon \in R$, we always have $L/R \supseteq L$. In your case $$ L/R = \{ a^{n_1} b^{n_2} : n_2 \leq n_1 \} \cup \{ a^n b^n a^{m_1} b^{m_2} : m_2 \leq m_1 \}. $$

$\endgroup$
  • $\begingroup$ Sir, why did you use $<=$ ? $\endgroup$ – Garrick Nov 2 '16 at 17:40
  • 1
    $\begingroup$ Since otherwise what I wrote would be incorrect. For example, $ab \in L/R$. $\endgroup$ – Yuval Filmus Nov 2 '16 at 17:42
  • $\begingroup$ Yes, i got my mistake ! But still little bit confused about, why < ? $\endgroup$ – Garrick Nov 2 '16 at 17:45

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.