# Noncontext free for quotient

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

• $L_1$ can also contain strings of the form $aabaaaabbaab$. Similarly $L_2$ can contain strings of the form $babbaabbbaaab$. – skankhunt42 Nov 20 '16 at 17:31
• Ah.. yea. Except that now I am even more confused, but - this is valid point – Timo Junolainen Nov 20 '16 at 17:35
• 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. – D.W. Nov 20 '16 at 18:18
• Yes, I might be talking too much. Exercise 3, users.utu.fi/jkari/automata/hw10.pdf – Timo Junolainen Nov 20 '16 at 18:26
• Not dumb, but it wasn't really a question. Both grammars are disregarding the Kleene's stars. – André Souza Lemos Nov 20 '16 at 23:53

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$.
• Why only strings of the form $a^*$? – skankhunt42 Nov 21 '16 at 6:11
• @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. – Hendrik Jan Nov 21 '16 at 23:12
• 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. – skankhunt42 Nov 22 '16 at 8:38
• @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. – Hendrik Jan Nov 23 '16 at 2:02