Write an efficient algorithm to decide expression-equivalence of two given programs.
If the expansion is literally infinite, that isn’t going to happen. Although I notice that you have written the expansion as a finite string that indicates infinity with ”...”.
The expansion is infinite, but it’s a repeating pattern, so we can use a finite representation (namely, the program itself). We don’t have to write the whole thing out in order to compare.
An analogy: we can represent infinite repeating strings by just writing a finite string, and then assuming it repeats. The analogous problem is then: decide whether two such strings represent the same infinite string. For instance, “abab” and “ababab” would represent the same infinite repeating string: “abababababab...”.
If the expansion is literally infinite, that isn’t going to happen. Although I notice that you have written the expansion as a finite string that indicates infinity with ”...”.
The expansion is infinite, but it’s a repeating pattern, so we can use a finite representation (namely, the program itself). We don’t have to write the whole thing out in order to compare.
An analogy: we can represent infinite repeating strings by just writing a finite string, and then assuming it repeats. The analogous problem is then: decide whether two such strings represent the same infinite string. For instance, “abab” and “ababab” would represent the same infinite repeating string: “abababababab...”.