Using the method of Theorem $3\mathrm{.}14$ to prove of disprove each of the following statements about$3\mathrm{.}4\mathrm{.}7$ The Test for a Regular$-$Expression Algebraic Law

Now, we can state and prove the test for whether or not a law of regular

expressions is truc. The test for whether $E=F$ is truc, where $E$ and $F$ are

two regular expressions with the same set of variables, is:

Convert $E$ and $F$ to concrete regular expressions $C$ and $D,$ respectively,

by replacing each variable by a concrete symbol.

Test whether $L(C)=L(D).$ If so$,$ then $E=F$ is a true law, and if not,

then the "law" is false. Note that we shall not see the test for whether two

regular expressions denote the same language until Section $4\mathrm{.}4.$ However,

we can use ad$-$hoc means to decide the equality of the pairs of languages

that we actually care about. Recall that if thc languages are not the same,

than it is sufficient to provide one countercxample: a single string that is

in one language but not the other.

Theorem $3\mathrm{.}14$: The above test correctly identifies the true laws for regular

expressions.

regular expressions.

$($a$)R(S+T)=RS+RT.$

$($b$)(R+S{)}^{**}=(R^{**}{S}^{**}{)}^{**}$

$($c$)(R+S{)}^{**}=R^{**}+S^{**}.$

$($d$)(RS+R{)}^{**}RS=(R{R}^{**}S{)}^{**}.$