Right quotient of $a^*baa^*$ with $ab^*$

60 Views Asked by At

Hello i am new to this concept. Take two languages:- $$L_1=a^*baa^*$$ $$L_2=ab^*$$ and $L_1/L_2$ (right quotient) would be $(a^*b + a^*baa^*)$?

Does this mean that suffix of $L_1$ and anything from $L_2$ I mean 'a' in $L_2$ which would be suffix of $L_1$ and hence we would remove it.)?

I searched internet and found this link but it is not clear to me how $L_1/L_2$ is $(a^*b + a^*baa^*)$.

1

There are 1 best solutions below

1
On

If $w_2\in L_2$ ends in $b$, $w_2$ can never be a suffix of any word $w_1\in L_1$ because $w_1$ must end with one or more $a$s. So $w_2$ must be $a$ to be a suffix of some $w_1$, and indeed $a$ is a suffix of every possible $w_1$, with the remainder consisting of the same $w_1$ but with one $a$ chopped off at the end.

From one or more $a$s at the end we get to zero or more $a$s. So the right quotient $L_1/L_2$ is $a^*ba^*$, which your $(a^*b+a^*baa^*)$ simplifies to.