# Formal grammar of MIU system

The MIU system, famous from Douglas Hofstadter, is a semi-thue system with the following rules:

Xi → Xiu
mX → mXX
XiiiY → XuY
XuuY → XY

and a start axiom "mi"

I have tried to find a formal grammar that generates all words that can be derived from the semi-thue system, but did not succeed. Is there a canonical way to construct/derive a formal grammar from a semi-thue system? Of course it is possible to convert it somehow, because semi-thue systems and unrestricted (type 0) grammars are congruent.

Any idea how the grammar for that particular example would look like?

• As far as I understand the MIU-rules is not a semi-Thue system. For a semi-Thue system we get rules $s\to t$ which can be applied to strings as follows $usv\to utv$. Thus the 3rd and 4th rule fit the scheme $ii\to u$ and $uu\to \varepsilon$. The first rule equals $i\to iu$ but can only be applied at the right end of the string. Most "problematic" is the second rule, as it contains a pattern: after left symbol $m$ we can duplicate the rest of the string. No doubt that can be translated into formal grammars, but whether it will be elegant remains to be seen. Aug 11 at 18:19

As Hendrik Jan remarked, the MIU-rules as a string rewriting system is not a semi-Thue system. Each string rewriting rule in a semi-Thue system does not care about context. A step of rewriting in a semi-Thue system consists of looking for a substring $$s$$, removing (forgetting) $$s$$ and inserting $$t$$ for some $$(s,t)$$ in a binary relation. However,

• Rule $$Xi \to Xiu$$ can only be applied when $$i$$ is at the end.
• Rule $$mX → mXX$$ can only be applied when $$X$$ is at the end. When applied, the rule has to remember what has been found, $$X$$.

It turns out the the MIU system generates the following regular language as proved here. $$\{w\in L(m\{i, u\}^*)\mid \text{the number of i's in } w\text{ is is divisible by }3 \}.$$

Here is a regular grammar for the language, where $$S_k$$ corresponds to the state of having $$k$$ $$i$$'s in the string.

$$S\to mS_0$$
$$S_0\to uS_0\mid iS_1$$
$$S_1\to uS_1\mid iS_2\mid\epsilon$$
$$S_2\to uS_2\mid iS_0\mid\epsilon$$