# Proving equality of two regular languages using operations closed under regular languages

Is there any way to prove that two regular languages A and B are equal using only closed operations under regular languages?

(The languages can be expressed as regular expressions,NFAs, eNFAs or DFAs)

Consider regular languages $$L_1, L_2,$$ and $$L_3$$. For $$\textbf{some}$$ closed unary operations $$*$$ and binary operations $$\diamond$$ on regular languages, $$(L_1)^* = (L_2)^* \Longrightarrow L_1=L_2 \\ L_1\diamond L_3 = L_2\diamond L_3 \Longrightarrow L_1=L_2$$ So showing that applying the same operation to two regular languages $$L_1$$ and $$L_2$$ produces equal regular languages may be enough to show that $$L_1$$ and $$L_2$$ are equal. However, this is not true for every operations. For this to be true, the operation $$\star:\mathscr{R}\rightarrow\mathscr{R}$$ must be one-to-one on $$\mathscr{R}$$, the set of all regular languages. Here is a breakdown of the most common closed operations on regular languages:

$$\textbf{One-to-one}$$:

• Complement of regular languages on same alphabet $$\Sigma$$ $$\Sigma^*-L_1=\Sigma^*-L_2 \implies L_1=L_2$$
• Reversal $$(R)$$ $$(L_1)^R=(L_2)^R \implies L_1=L_2$$
• One-to-one homomorphism $$(h)$$ $$h(L_1)=h(L_2) \implies L_1=L_2$$

$$\textbf{Not one-to-one}$$:

• Union $$(\cup)$$ with another regular language $$L(a^*)\cup L(a^*b^*) = L(b^*)\cup L(a^*b^*) \\ L(a^*)\ne L(b^*)$$
• Intersection $$(\cap)$$ with another regular language $$L(b^*)\cap L(b^*) = L(a^*b^*)\cap L(b^*) \\ L(b^*)\ne L(a^*b^*)$$
• Concatenation $$(\circ)$$ with another regular language $$L(ab^*)\circ L(b^*) = L(a)\circ L(b^*) \\ L(ab^*)\ne L(a)$$
• Kleene closure $$(*)$$ $$L(b)^* = L(bb^*)^* \\ L(b) \ne L(bb^*)$$
• Difference $$(-)$$ with another regular language $$L(a^*)- L(a^*b^*) = L(b^*)-L(a^*b^*) \\ L(a^*)\ne L(b^*)$$