In a MIU puzzle, either of the letters M, I or U could go as a start symbol.…

Concept

A production (rewriting) system consists of a start string (axiom) and a set of rules that each rewrite one string into another. A string is a “valid word” (a theorem) of the system if and only if it can be reached from the axiom by a finite sequence of rule applications; the number of “transformations” is the length of that sequence. Two useful facts about such systems: a rule that only ever inserts symbols can never be undone by another insert-only rule, and doubling a string exactly reproduces whatever pattern (clean or corrupted) the string already has.

Application to this MIU system

Here the axiom is MIU, i.e. M followed by x = “IU”. Rule R₂ (M.x → M.x.x) doubles the suffix after M, and Rule R₁ (U → IU) inserts one extra I immediately in front of a chosen U.

1. Apply R₂ to MIU (x = IU): suffix doubles from “IU” (1 copy) to “IUIU” (2 copies) → MIUIU.

2. Apply R₂ again (x = IUIU): suffix doubles from 2 copies to 4 copies → MIUIUIUIU.

3. Apply R₂ again (x = IUIUIUIU): suffix doubles from 4 copies to 8 copies → MIUIUIUIUIUIUIUIU.

So pure R₂-doubling, starting from 1 copy of “IU”, only ever reaches 1, 2, 4, 8, 16, … copies — powers of 2 — and the string stays a perfectly clean, alternating block of IU pairs at every stage.

Now look at R₁ on such a clean string. In any clean block of n IU-pairs, every U already has its own I immediately to its left. Replacing that U with IU inserts one more I right before it, producing an adjacent “II” at that spot. Since neither rule can delete a symbol, this “II” can never be removed afterwards, and R₂ only duplicates whatever suffix currently exists — it duplicates the corruption too, it cannot repair it. So the instant R₁ is used on a clean IU-block, the string can never again equal a clean, uniformly alternating M+(IU)ⁿ string.

Consequently, the only values of n for which M+(IU)ⁿ is derivable at all are exactly n = 1, 2, 4, 8, 16, … — the powers of 2 reachable by R₂-doubling alone.

Cross-check on the two given strings

(i) MIUIUIUIUIU has n = 5 copies of “IU” after M (5 is not a power of 2), so this string can never be derived: no sequence of R₁/R₂ applications reaches it.

(ii) MIUIUIUIUIUIUIUIU has n = 8 copies of “IU” after M, and 8 = 2³, so this string IS derivable, in exactly 3 transformations (three applications of R₂, doubling 1→2→4→8), as shown above.

As an independent check, try to reach n = 5 by inserting with R₁ instead of only doubling: starting from n = 4 (“IUIUIUIU”) and applying R₁ to its last U gives “IUIUIUI” + “IU” = “IUIUIUIIU” — a 9-symbol string with an “II” in it, not the clean 10-symbol n = 5 pattern “IUIUIUIUIU”. This confirms n = 5 is unreachable by any combination of the two rules, corroborating the argument above.

So exactly one of the two strings, (ii), is a valid word, while (i) is not — they do not share the same derivability status, so no comparison of “number of transformations” between them is even meaningful.

Result

Exactly one of (i) and (ii) — namely (ii) — is a valid word of this system, and the other, (i), is not. This matches: “Either (i) or (ii) but not both of these are valid words.”