# Regular language properties

For regular languages $R, S$ and $T$, which of the following are true?

1. $R \cup S = S \cup R$
2. $(R \cup S) \cdot T = RT \cup ST$
3. $R^* \cdot S^* = (R \cup S)^*$
-
What have you done to try and prove these? Where are you getting stuck? What do you think? – Dave Clarke Feb 14 '13 at 16:44
So you want a yes/no answer for each? – Paresh Feb 14 '13 at 17:17
Languages are also sets. Proving equivalence of sets is done by proving inclusion in both directions. – saadtaame Feb 14 '13 at 17:25

1. True
2. True
3. False

To find the proofs, proceed as follows:

1. Show that any string $x \in R \cup S$ belongs to $S \cup R$, and vice versa.
2. Ditto 1.
3. Find a string $x$ that is in $(R \cup S)^*$ but not the LHS. Hint: what about $rsr$ where $r \in R, s \in S$?
-
1. $x\in R\cup S \iff x\in R \vee x \in S \iff x\in S \vee x \in R \iff x\in S\cup R$

2. $x\in(R\cup S)T \iff \exists u, v \mid (x=uv)\wedge (u \in R\cup S)\wedge (v\in T) \iff \exists u, v \mid (x=uv)\wedge (u \in R \vee u \in S)\wedge (v\in T) \iff \exists u, v \mid (x=uv)\wedge (u\in R \wedge v\in T) \vee (u\in S \wedge v\in T) \iff \exists u, v \mid (x=uv)\wedge (x\in RT)\vee (x\in ST)\iff x\in RT\cup ST$.

3. Let $R=\{0\}$ and $S=\{1\}$.

-
+1 for the formal proofs – Romuald Feb 14 '13 at 21:53
@Romuald Thanks! – saadtaame Feb 14 '13 at 23:07