4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$
    – Hendrik Jan
    Aug 11, 2022 at 18:19

1 Answer 1

Reset to default
4
$\begingroup$

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$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.