1

I am showing that two regular expressions are equal. In one of intermediate steps, I thought of the equaility: $$(RS+R)^* = (RS)^*R(RS)^*R(RS)^*....R(RS)^* = R^*(RS)R^*(RS)...R^*$$

Is it true? I mean, can I use it in my proof steps?

Jnau.Ch
  • 11
  • It’s certainly true that $(RS+R)^=((RS)^R)^(RS)^=(R^RS)^R^*$; whether you can use it without proof depends on your instructor and on what’s already been proved. – Brian M. Scott Oct 25 '14 at 20:28
  • Anything with ... is not a good regular language definition, so it is hard to prove that the two are equal regular languages. – Thomas Andrews Oct 25 '14 at 20:30
  • @BrianM.Scott Is there any better equality for $(S+T)^*$ ? – Jnau.Ch Oct 25 '14 at 20:37
  • $(S^T)^S^$ and $(T^S)^T^$ and the analogues with the extra factor on the left are certainly the simplest that occur to me at the moment. – Brian M. Scott Oct 25 '14 at 20:42

0 Answers0