I was studying the given finite automaton. 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?
This is the method I am referring as $R^{(k)}_{ij}$ method.
One approach is to use known identities for regular expressions, such as
as rewriting steps, to find a chain of steps that rewrites the first expression into the second.
Arto Salomaa published two sets of such identities in 1966; these sets are infinite, which is inevitable, as Volodymyr Redko had shown.
So this approach is not always practical, it is not very clear how to do this in a systematic way, and I cannot see how easy it will be for this case.
The following alternative approach feels like cheating, but it is deterministic, and it will always work:
This can be expensive (the DFA can be doubly exponentially larger than the original expression), but at least it works.
$R^*S(U+TR^*S)^* = R^*SU^*(TR^*SU^*)^*$ since, $[(a+b)^* = b^*(ab^*)^*]$ $R^*SU^*(TR^*SU^*)^* = (R^*SU^*T)^*R^*SU^*$ since, $[a(ba)^* = (ab)^*a]$ $(R^*SU^*T)^*R^*SU^* = R^*(SU^*TR^*)^*SU^*$ since, $[a(ba)^* = (ab)^*a]$ $R^*(SU^*TR^*)^*SU^* = (R+SU^*T)^*SU^*$ since, $[(a+b)^* = b^*(ab^*)^*]$
The easiest method might be just to prove that both expressions define the same language as the automaton you started with. This is quite straightforward, and you have done half of the work already.
Specifically, $R+SU^*T$ is the expression for “go from the start state to the start state with all intermediate states being the other state”, and $SU^*$ the expression for “go from the start state to the final state without ever going back”, yielding $(R+SU^*T)^*SU^*$. I believe this is exactly what you call the “$R_{ij}^{(k)}$ method”—you just use a different implicit ordering of the states. (The general method is described here.)
