patternMinor
Semi-Thue system, which terminates
Viewed 0 times
semithuesystemwhichterminates
Problem
I observed that with rewrite rules:
$abb \rightarrow bab $
$baa \rightarrow aba $
Every derivation ends, moreover, if there is same amount of $a$'s and $b$'s in input, then derivation ends in $(ab)^+(ba)^$.
Why do these two properties hold?
$abb \rightarrow bab $
$baa \rightarrow aba $
Every derivation ends, moreover, if there is same amount of $a$'s and $b$'s in input, then derivation ends in $(ab)^+(ba)^$.
Why do these two properties hold?
Solution
Consider the potential function
$$
\Phi(w_1 \ldots w_n) = \sum_{i=2}^n 2^i 1_{w_i = w_{i-1}}.
$$
Applying one of the rewrite rules always decreases the potential: if we change $abb$ to $bab$ at positions $i,i+1,i+2$, then we lost $2^{i+2}$ and might have gained $2^i$. Since the potential is non-negative, every derivation ends.
Suppose now that the initial word contained an equal number of $a$'s and $b$'s. The same is true for the final word, since the rules don't change the number of $a$'s or $b$'s. It therefore suffices to prove that any word that has $n$ letters $a$ and $n$ letters $b$, and doesn't contain $abb$ or $baa$, has the form $(ab)^n$ or $(ba)^n$. We prove this by induction.
The base cases $n=0,1$ are trivial, so suppose that $n \geq 2$. Assume without loss of generality that the final word ends with $b$. It must have a suffix of the form $ab^k$ (since it contains at least one $a$). Since it contains no $abb$, we must have $k = 1$. Remove the suffix $ab$ and apply induction to deduce that the word is either $(ab)^n$ or $(ba)^{n-1}ab$. The latter case cannot happen since it contains $baa$, and so the word must be $(ab)^n$.
We can slightly strengthen this result by noticing that the rewrite rules never change the final letter of the word. So we reach $(ab)^$ if the original word terminated with $b$, and reach $(ba)^$ otherwise.
$$
\Phi(w_1 \ldots w_n) = \sum_{i=2}^n 2^i 1_{w_i = w_{i-1}}.
$$
Applying one of the rewrite rules always decreases the potential: if we change $abb$ to $bab$ at positions $i,i+1,i+2$, then we lost $2^{i+2}$ and might have gained $2^i$. Since the potential is non-negative, every derivation ends.
Suppose now that the initial word contained an equal number of $a$'s and $b$'s. The same is true for the final word, since the rules don't change the number of $a$'s or $b$'s. It therefore suffices to prove that any word that has $n$ letters $a$ and $n$ letters $b$, and doesn't contain $abb$ or $baa$, has the form $(ab)^n$ or $(ba)^n$. We prove this by induction.
The base cases $n=0,1$ are trivial, so suppose that $n \geq 2$. Assume without loss of generality that the final word ends with $b$. It must have a suffix of the form $ab^k$ (since it contains at least one $a$). Since it contains no $abb$, we must have $k = 1$. Remove the suffix $ab$ and apply induction to deduce that the word is either $(ab)^n$ or $(ba)^{n-1}ab$. The latter case cannot happen since it contains $baa$, and so the word must be $(ab)^n$.
We can slightly strengthen this result by noticing that the rewrite rules never change the final letter of the word. So we reach $(ab)^$ if the original word terminated with $b$, and reach $(ba)^$ otherwise.
Context
StackExchange Computer Science Q#66769, answer score: 4
Revisions (0)
No revisions yet.