Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)^*$
share|cite|improve this question
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$?
share|cite|improve this answer
  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\}$.

share|cite|improve this answer
+1 for the formal proofs – Romuald Feb 14 '13 at 21:53
@Romuald Thanks! – saadtaame Feb 14 '13 at 23:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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