How to show R*S(U+TR*S)* is equivalent to (R+SU*T)SU*?

[PLAGUE]

TL;DR

How to show R*S(U+TR*S)* is equivalent to (R+SU*T)SU* using regular expression algebra?

I was studying the given finite automata. Using $$R_{ij}^{(k)}$$ method, I found out that the Regular Expression that this automaton accepts is $$R^*S(U+TR^*S)^*$$. But my book says, the regular expression for the accepted strings can be described
in various ways. One is $$(R+SU^*T)SU^*$$.

How do I show that these two regular expressions are equivalent?

 

[SSequence]

I don't know, but I am having difficulty seeing how $(R+SU^*T)SU^*$ can really be a correct expression? I mean consider any string accepted by the automaton you posted such that it contains at least 2 or more $R$'s. For example, consider the string $RRS$. It is accepted by the automaton but I can't see how it can be generated by the expression $(R+SU^*T)SU^*$ ?

 

[Filip Larsen]

I think the OP must have a typo in the second expression, missing a repeat.

 

[pbuk]

I was studying the given finite automata. Using $$R_{ij}^{(k)}$$ method, I found out that the Regular Expression that this automaton accepts is $$R^*S(U+TR^*S)^*$$. But my book says, the regular expression for the accepted strings can be described
in various ways. One is $$(R+SU^*T)SU^*$$.

Firstly, $LaTeX$ is not helpful for posting regular expressions; for instance it makes + look like a binary operator.

Neither of the regular expressions you post correctly describe the diagram: @SSequence has posted a string that is incorrectly rejected by the second expression (R+SU*T)SU* and the string STS is incorrectly rejected by the first expression.

 

[PLAGUE]

Sorry. The second expression should be $$(R+SU^*T)SU^*$$

 

[PLAGUE]

TL;DR: How to show R*S(U+TR*S)* is equivalent to (R+SU*T)SU* using regular expression algebra?

I was studying the given finite automata. Using $$R_{ij}^{(k)}$$ method, I found out that the Regular Expression that this automaton accepts is $$R^*S(U+TR^*S)^*$$. But my book says, the regular expression for the accepted strings can be described
in various ways. One is $$(R+SU^*T)SU^*$$.

How do I show that these two regular expressions are equivalent?View attachment 371244

Sorry. The second expression should be $$(R+SU^*T)SU^*$$

 

[pbuk]

One is $$(R+SU^*T)SU^*$$.

Sorry. The second expression should be $$(R+SU^*T)SU^*$$

Sorry. The second expression should be $$(R+SU^*T)SU^*$$

You keep posting the same obviously incorrect expression. And you keep posting it using $LaTeX$ math notation which is completely inappropriate.

The expression is obviously incorrect because the first node of the diagram

View attachment 371244

is clearly R* not R+.

I was studying the given finite automata.

Studying from what source? Please provide a reference.

 

[PLAGUE]

Sorry. The second expression should be, $$(R+SU^*T)^*SU^*$$

 

[pbuk]

(R+SU*T)*SU* incorrectly rejects STS. Perhaps you intended to post (R*SU*T)*SU*?

Note that as I posted in #5 the string STS is also incorrectly rejected by your first expression R*S(U+TR*S)* due to a similar error - U+ in this expression should be U* if it is to correctly encode the diagram. Do you understand the difference between the Kleene Star * and the Kleene Plus +?

I ask you again, what is the source for this material?

 

[Filip Larsen]

the difference between the Kleene Star * and the Kleene Plus +?

Comparing with the diagram, I read use of symbol + in any of OP posts to really indicate RE alternation and not Kleene plus, that is, (R|SU*T)SU* with the normal operator precedence.

Edit: removed double words.

 

[pbuk]

Comparing with the diagram the diagram, I read use of symbol + in any of OP posts to really indicate RE alternation and not Kleene plus, that is, (R|SU*T)SU* with the normal operator precedence.

Thanks, that also explains the use of $LaTeX$ math formatting. It is a shame that we have had to figure this out for ourselves because the OP has not provided any reference.

So, to paraphrase the OP with the corrected second expression, the question is:

How can I prove the equivalence of $R^*S(U+TR^*S)^*$ and $(R+SU^*T)^*SU^*$?

Well by definition two REs are equivalent if they describe the same FA so here this is trivial. Another way of proving equivalence is by transforming the REs to a common form using equivalences such as $(a + b)^* = a^* (ba^*)^*$. @PLAGUE is this what you are trying to do? Please show your efforts so far.

 

[SSequence]

I think this multiple use of $+$ is very common. Now I don't know whether the newer texts use this or not, but at least in the older texts that was the case.

For example, if the alphabet is $\Sigma=\{a,b\}$, an expression like $(a+b).a^{+}$ would mean the following language: $\{aa,aaa,aaaa,.......\} \cup \{ba,baa,baaa,......\}$

 

[pbuk]

I think this multiple use of $+$ is very common

Possibly, but I had forgotten its use for alternation.

Now I don't know whether the newer texts use this or not, but at least in the older texts that was the case.

I think Conway's 1971 book did, but other old texts I am familiar with use $\cup$ for alternation. Kleene's original 1956 paper used $\lor$. But now I think $|$ is pretty much universal.

Anyway now we have resolved what the OP actually meant, and got them to correct some errors perhaps we should get back on-topic.

 

[PLAGUE]

(R+SU*T)*SU* incorrectly rejects STS. Perhaps you intended to post (R*SU*T)*SU*?

Note that as I posted in #5 the string STS is also incorrectly rejected by your first expression R*S(U+TR*S)* due to a similar error - U+ in this expression should be U* if it is to correctly encode the diagram. Do you understand the difference between the Kleene Star * and the Kleene Plus +?

I ask you again, what is the source for this material?

https://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation

Edition 3rd page 99

 

[PLAGUE]

(R+SU*T)*SU* incorrectly rejects STS. Perhaps you intended to post (R*SU*T)*SU*?

Note that as I posted in #5 the string STS is also incorrectly rejected by your first expression R*S(U+TR*S)* due to a similar error - U+ in this expression should be U* if it is to correctly encode the diagram. Do you understand the difference between the Kleene Star * and the Kleene Plus +?

I ask you again, what is the source for this material?

+ means or here. You may be familiar with |

 

[pbuk]

https://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation

Edition 3rd page 99

At last!

So to return to your original question...

How do I show that these two regular expressions are equivalent?

There are three ways to do this:

1. show that that they are both implemented by the same automaton - which is tautologically true here
2. test with all possible strings in the language
3. algebraic transformation - you will learn about this in section 3.4

For now, I would stick with the tautology.