Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
7  
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
2  
Languages are also sets. Proving equivalence of sets is done by proving inclusion in both directions. –  saadtaame Feb 14 '13 at 17:25
add comment

2 Answers

  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|improve this answer
add comment
  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|improve this answer
    
+1 for the formal proofs –  Romuald Feb 14 '13 at 21:53
    
@Romuald Thanks! –  saadtaame Feb 14 '13 at 23:07
add comment

Your Answer

 
discard

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.