Find initial expression that a reduction process with 2 rules does not terminate

Question

Imagine a language of finite sequences of 0 and 1. The rules for simplifying strings in this language are given by:

l??x => x1101

0??x => x00

In these rules, the variable x denotes an arbitrary sequence of 0s and Is and the sign '?' denotes a single 0 or 1. Construct an expression for which the reduction process does not terminate.

I have across this problem in "Introduction to Functional Programming" by Richard Bird, and I can't find the solution. Can someone guide me on the methology to solve this?

Answer 1

im not sure if this is correct, but ive written this:

The expression ('10100') creates a loop. Explained:

With the expression '10100', the x is always a binary of either '101' or '00',and since both rules can be only applied to one of each, the rules are applied endelessly.

Since x is always equal to either '00' or '101', it happens that, when the 1st digit is '0', the 2nd is also '0' and the following digits are '1101' which results from the application of the 1st rule. When the first digit is '1', which only occurs when x is '101', the following digits are '00', which results from the application of the 2nd rule.

So, with 10100 the reduction proccess goes as follows:

10100    (APPLY RULE 1)

001101   (APPLY RULE 2)

10100    (APPLY RULE 1)

001101