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

Question

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)

Answer 1

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^*) $$