5
$\begingroup$

/// is an esoteric language, and I thought of posting a code-golf problem related to it.

A /// program of the form /p/q/r where p, q, and r are strings that do not contain / or \ does:

  1. If the string p is a substring of r, go to step 2; otherwise step 5.
  2. Replace the leftmost occurrence of p in r with q.
  3. Let the result of step 2 be the new r.
  4. Go to step 1.
  5. Output r and halt.

In step 1, an empty string shall be a substring of any strings.

For simplicity I am thinking each of p, q, r consisting of zero or more a's and b's.

At first I thought the following algorithm would work:

  1. Returns no if p is both a substring of q and r; otherwise yes.

But that was wrong; /ab/bbaa/abb can be one of the exceptions, as "ab" does not appear in "bbaa" but in "abb".

I am suspecting it's possibly impossible to make an algorithm to solve this problem. Is it solvable?

$\endgroup$

1 Answer 1

4
$\begingroup$

According to this Math Overflow answer, the answer is not known as of 2014.

It seems your problem can be restated to asking if the termination of one-rule string-rewriting systems is decidable. A rule of a string-rewriting system is a substitution like the one you gave with $ab\to bbaa$.

Even though the Math Overflow answer doesn't distinguish between alphabet size, which in your case is only 2 consisting only of $\{a,b\}$, you can convert a SRS with a larger alphabet into one with only 2 letters, thus making their termination problems equivalent. Basically, give each letter a unique index $n$, then replace it with $ab^na$ in both the input string as well as the rules. So for example $cad→addc$ can be encoded as $abbbaabaabbbba→abaabbbbaabbbbaabbba$.

$\endgroup$
1
  • 1
    $\begingroup$ The fastest-growing terminating such rule I could find so far was $ab→bba$ on the input $a^nb$, which grows exponentially in $n$. $\endgroup$
    – user41805
    Jul 5, 2021 at 9:53

Your Answer

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