Find two non-empty languages whose concatenation is equal to another language

Question

Let $L=\{a,b,ab,ba,bb,aab,bab,baab\}$. Find two Languages $L_1$ and $L_2$, both not equal to $\{\lambda\}$ over the Alphabet $\{a,b\}$ such that

$$L_1\cdot L_2=L.$$

The solution is $L_1=\{a,b,ba\}$, $L_2=\{\lambda, b, ab\}$.

Do you know a systematic way to always find the solution (or disprove the existence) for such a problem? I really can't see the process behind arriving to such a solution.

I tried to draw graphs with an "is-prefix-of" and "is-suffix-of" relation but that didn't get me to explain the solution.

Answer 1

I can’t give you an algorithm, but I can suggest how I might attack this particular problem. The words that begin with $b$ and are at least two letters long are $ba,bb,bab$, and $baab$, making up fully half of $L$, so I experiment with the possibility of putting $b$ in $L_1$ and $a,b,ab$, and $aab$ in $L_2$. Now

$$\{b\}\cdot\{a,b,ab,aab\}=\{ba,bb,bab,baab\}\;,$$

which at least doesn’t give me any unwanted words, and I still need to take care of $a,b,ab$, and $aab$. But these are exactly the words currently in $L_2$, so adding $\lambda$ to $L_1$ will do the job nicely: setting $L_1=\{\lambda,b\}$ and $L_2=\{a,b,ab,aab\}$ gives me a solution, albeit a different one from the one that you have.

Answer 2

We want to find a list of prefixes and suffixes that form the words in $L$. We traverse the words in $L$ from left to right and add letters to $L_1$ and $L_2$ as needed. $L_1$ and $L_2$ start as empty sets.

Starting with $a$ I can form this as $a\lambda$ so I add $a$ to $L_1$ and $\lambda$ to $L_2$. Next, I want to get $b$ so I have two choices:

$1.$ I can add $b$ to $L_1$ and since I already have $\lambda$ in $L_2$ I get $b\lambda=b$ in $L$

$2.$ I can add $\lambda$ to $L_1$ and $b$ to $L_2$. The problem with this approach is that I now have $\lambda$ in both $L_1$ and $L_2$ but I don't have $\lambda\lambda=\lambda$ in $L$. Therefore, I must go with option $1$

So far I have $L_1=\{a, b\}$ and $L_2=\{\lambda\}$

I want $ab$ so I add $b$ to $L_2$ to get $L_1=\{a, b\}$ and $L_2=\{\lambda, b\}$

Now I want $ba$ and since I already have $b$ in $L_1$ it is tempting to just add $a$ to $L_2$. The problem with that is we would need $aa$ in $L$ which is not the case so we add $ba$ to $L_1$ to get $L_1=\{a, b, ba\}$ and $L_2=\{\lambda, b\}$.

So far, $L_1\cdot L_2=\{a, b, ba, ab, bb, bab\}$

I am missing $aab$ and $baab$ so I add $ab$ to $L_2$ to arrive at the final answer of $L_1=\{a, b, ba\}$ and $L_2=\{\lambda, b, ab\}$.