Cheap and Secure Web Hosting Provider : See Now

Noncontext free for quotient

, , No Comments
Problem Detail: 

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

Asked By : Timo Junolainen

Answered By : Hendrik Jan

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/66252

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback