1
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.