HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Formal grammar of MIU system

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
formalsystemmiugrammar

Problem

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?

Solution

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$

Context

StackExchange Computer Science Q#153529, answer score: 4

Revisions (0)

No revisions yet.