patternMinor
Formal grammar of MIU system
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?
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,
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$
- 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.