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$

1 Answer 1

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$
3
  • $\begingroup$ Sir, why did you use $<=$ ? $\endgroup$
    – Garrick
    Commented Nov 2, 2016 at 17:40
  • 1
    $\begingroup$ Since otherwise what I wrote would be incorrect. For example, $ab \in L/R$. $\endgroup$ Commented Nov 2, 2016 at 17:42
  • $\begingroup$ Yes, i got my mistake ! But still little bit confused about, why < ? $\endgroup$
    – Garrick
    Commented Nov 2, 2016 at 17:45

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.