1
$\begingroup$

Have such exercise: Let $L_1=\{a^{2n}b^n|n\geq1\}^*$

and $L_2=\{b^na^n|n\geq 1\}^*b$

Prove, that $L_1, L_2$ are context free, while quotient $L_1/L_2$ is not context-free.

(This is home exercise, which I am not sure what to make of it. 3rd one)

Anyway, proving $L_1, L_2$ are CFL is trivial.

For $L_1$:

S->aaSb|$\epsilon$

For $L_2$

S->Ab

A->bAa|$\epsilon$

So far so good, grammar can be constructed, i.e CFL. Fine.

But quotient.. Lets list few words for $L_1$: $\epsilon$ then: aab, aabaab, aabaabaab, $\dots$ then aaaabb, aaaabbaaaabb, $\dots$ and so on - string under Kleene, which contains twice as much $a$ than $b$

Now about $L_2$ words: b then bab,babab,bababab,$\dots$ then bbaab,bbaabbaab,$\dots$, ie - $(b^na^n)^*b$

But.. Only words in $L_1$ are of format which ends in suffix ...ab are where $n=1$: $aab,aabaab,\dots$, moreover - if we take string from $L_1$, for example $aabaab$, we kinda remove trailing $b$ ($aabaa$), after which we can't really remove anything else, in this particular case we would have to remove suffix $bbaa$, but there is no such suffix in word from $L_1$

So, all in all - quotient, to my understanding is $L_1$, with only difference that there is very last b always removed. And it feels to me like CF, what am I doing wrong?

Edit: According to comment, I have mistake in my thoughts, which is reasonable, we dont have to Kleenize $n$ in each substring.

Ie $aaaabbaab$ for $L_1$ is possible. Ok, now lets look exactly at $aaaabbaab$ - first remove trailing $b$, get $aaaabbaa$. Now $bbaa$ - resulting in $aaaa$.. So all in all, quotient is still $L_1$, which has some arbitrary suffix removed. Still feels CF to me

|cite|improve this question
$\endgroup$
  • $\begingroup$ $L_1$ can also contain strings of the form $aabaaaabbaab$. Similarly $L_2$ can contain strings of the form $babbaabbbaaab$. $\endgroup$ – skankhunt42 Nov 20 '16 at 17:31
  • $\begingroup$ Ah.. yea. Except that now I am even more confused, but - this is valid point $\endgroup$ – Timo Junolainen Nov 20 '16 at 17:35
  • $\begingroup$ What exactly is your question? It's hard for me to tell what question you are looking to have answered and what kind of answer you are looking for. $\endgroup$ – D.W.♦ Nov 20 '16 at 18:18
  • $\begingroup$ Yes, I might be talking too much. Exercise 3, users.utu.fi/jkari/automata/hw10.pdf $\endgroup$ – Timo Junolainen Nov 20 '16 at 18:26
  • 1
    $\begingroup$ Not dumb, but it wasn't really a question. Both grammars are disregarding the Kleene's stars. $\endgroup$ – André Souza Lemos Nov 20 '16 at 23:53
1
$\begingroup$

Work backwards, from right to left. Try to find which strings of the form $a^*$ belong to $L_1/L_2$. So find matches of strings $w_1\in L_1$ and $w_2\in L_2$ such that at the start only a string of the form $a^*$ sticks out: $w_1= a^k w_2$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why only strings of the form $a^*$? $\endgroup$ – skankhunt42 Nov 21 '16 at 6:11
  • $\begingroup$ @skankhunt42 Good question. To me it seems more easier to handle. When restricting to $a$'s only we get a simple solution, and a very clear non-context-free language. Technically this means we intersected the quotient that we obtain by the regular language $a^*$: this does not change the (non-)context-freeness. $\endgroup$ – Hendrik Jan Nov 21 '16 at 23:12
  • $\begingroup$ That doesn't seem right to me. Suppose $L = \{b^p \mid p \text{ is a prime number}\} \cup L(a^*)$. Then if we take intersection with $L(b^*)$, we get a non-context-free language. However, intersection with $L(a^*)$ gives us a context-free language. $\endgroup$ – skankhunt42 Nov 22 '16 at 8:38
  • $\begingroup$ @skankhunt42 Formulated that way you are right. What I meant here is that context-free languages are closed under intersection with regular languages. If we intersect with $a^*$ in this construction we get a non-context-free language, so indeed the original language must be non-context-free either. $\endgroup$ – Hendrik Jan Nov 23 '16 at 2:02

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.