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 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.