Subset division

Question

I am trying to remove the first symbol "a" from this set $L=(a,b,c)^* \cdot (ab,bc) \cdot (a,b,c)^* $ where these sets represent strings and $(a,b,c)^*$ means all combinations of letters a,b,c with plus the empty set and $\cdot$ is the concatenation .So in order to find the result without "a" of L ,I should iterate over every set of L meaning : if the first $(a,b,c)^*$ is not empty the result is $L$ ,else the result is $ (b) \cdot (a,b,c)^*$,so once I find a set that is not in the form $( ... )$ containing finite words like this one $(ab,bc)$ I should stop and unite all results meaning the answer is : $L \cup (b) \cdot (a,b,c)^* $ ,so is it correct to stop there? Also if the operation was $\cup$ instead of $\cdot$ we should check for all sets no matter what and unite them?

Answer 1

Given a language $L$ of $A^*$ and a letter $a$, you want to compute the language $$ a^{-1}L = \{u \in A^* \mid au \in L \} $$ This can be done inductively by using the following formulas, where $1$ denotes the empty word: \begin{align} a^{-1}(L_1 \cup L_2) &= a^{-1}L_1 \cup a^{-1}L_2,\\ a^{-1}(L_1L_2) &= \begin{cases} (a^{-1}L_1)L_2 &\text{if $1 \notin L_1$,}\\ (a^{-1}L_1)L_2 \cup a^{-1}L_2 &\text{if $1 \in L_1$}\\ \end{cases}\\ a^{-1}L^* &= (a^{-1}L)L^* \end{align} Also note the useful formulas $a^{-1}(L_1 \setminus L_2) = a^{-1}L_1 \setminus a^{-1}L_2$ and $a^{-1}(L_1 \cap L_2) = a^{-1}L_1 \cap a^{-1}L_2$.

Coming back to your language $L = A^*(ab \cup bc)A^*$, you get \begin{align} a^{-1}(A^*(ab \cup bc)A^*) &= (a^{-1}A^*)((ab \cup bc)A^*) \cup a^{-1}((ab \cup bc)A^*)) \\ &= A^*(ab \cup bc)A^* \cup (a^{-1}(ab \cup bc))A^* \\ &= A^*(ab \cup bc)A^* \cup (a^{-1}(ab) \cup a^{-1}(bc))A^* \\ &= A^*(ab \cup bc)A^* \cup (b \cup \emptyset)A^* \\ &= A^*(ab \cup bc)A^* \cup bA^* \end{align} Of course, this is very detailed and with a little bit of practice, you will obtain the result much faster.