Is my proof of 2 languages equality correct?

Question

I started to self-study the formal languages theory, and tried to solve the following problem:

Problem

Prove, that these 2 languages are equivalent:

$$ \Sigma = \{a,b,c\}\\ L_1 = \{(abc)^na | n \ge 2\},\\ L_2 = \{ab(cab)^nca|n \ge 1\}\\ $$

Solution

At first I tried to manually generate several words from these languages:

|        L1                |       L2                 |
| abc abc a, n = 2         | ab cab ca, n=1           |
| abc abc abc a, n = 3     | ab cab cab ca, n =2      |
| abc abc abc abc a, n = 4 | ab cab cab cab ca, n = 3 |

they are identical. Then the general case

\begin{multline*} L_2 = \{ab(cab)^nca|n \ge 1\} = ab(cab)^nca = ab \;\overbrace{cab \cdot cab \ldots cab}^{n\:times} \; ca = \\\overbrace{abc \cdot abc \ldots abc}^{n+1\:times} \; a = \{(abc)^na | n \ge 2\} = L_1\\ \end{multline*} \begin{multline*} L_1 = \{(abc)^na | n \ge 2\} = (abc)^na = \overbrace{abc \cdot abc \ldots abc}^{n\:times}a = \\ab\; \overbrace{cab \cdot cab \ldots cab}^{n - 1\:times}\;ca = \{ab(cab)^nca|n \ge 1\} = L_2 \end{multline*}

• Is my proof correct?
• Are there any formal rules for such languages transformations, so I could manipulate them like algebraic equations? Maybe, I can use product or sum ($\Pi, \Sigma$) with indices instead of my clumsy notation?

Answer 1

Yes, your proof is correct.

One simpler way to write it may be to note that taking any element from $L_1$ and pre-pending $abc$ to it results in another element from $L_1$. Also you can easily show by induction that every element of $L_1$ comes from pre-pending $abc$ some number times to the smallest (in length) element of $L_1$. The same statements are true for $L_2$ as well.

Now all that remains to be done is to verify that the smallest elements of the two languages are the same, which is extremely simple.

Answer 2

Yes your solution is actually elegant! although redundant! you wrote twice the same thing. So take one of those equations and you are done. Very nice

Since you asked for general ideas:

you always can take a generic element from one of the languages, and try to write it as an element of the other language and vice versa. In this case it almost boils down to what you did.