How to prove that $(L_1L_2)' = (L_2)'(L_1)'$

85 Views Asked by At

How to prove that $(L_1L_2)' = (L_2)'(L_1)'$

$(L)'$ denotes the reverse of $L$.

I think using mathematical induction, it can be shown true for two languages $L_1$ and $L_2$ of length $1$ each and then do induction using one of the lengths and then repeat with the other length. Is there any other way of proving this in a simpler way without making it too big with induction method?

1

There are 1 best solutions below

0
On

Let $x\in (L_1L_2)'$ then there exist $w_1 \in L_1$ and $w2\in L2$ such that $$x = \mathrm{reverse}(w1w2) = \mathrm{reverse}(w2) \mathrm{reverse}(w1) \in (L_2)'(L_1)'$$

All those statements work both ways, so you get that $x\in (L_1L_2)' \iff x\in (L_2)'(L_1)'$