# Is it possible to derive a string in this rewriting system?

Rewriting system is a set of rules in the form of $A \leftrightarrow B$. If we apply that rule to a string $w$ we replace any substring $A$ in $w$ with a substring $B$ and vice versa.

Given a starting string $AAABB$ can we derive $BAAB$ in the system with the following rules:

• $A \leftrightarrow BA$
• $BABA \leftrightarrow AABB$
• $AAA \leftrightarrow AB$
• $BA \leftrightarrow AB$

Is there a general algorithm for that?

• I would appreciate if you could add more tags to this question, or change the rule set to make it look cooler. Mar 16 '12 at 5:07
• @J.D. I think, in general, this rewriting problem can't be solved, because you can model Turing machine with such a rewriting system and derivation problem == halting problem in TM Mar 16 '12 at 5:57
• @J.D. ah, that makes sense, I should read more into it, thanks! Mar 16 '12 at 6:58
• @Daniil and future readers: The undecidable problem used is the Post correspondence problem.
Notice that the parity of the number of $A$s does not change. Since one string contains an odd number $A$ and the other even, they are not reachable.
I believe in general (for an arbitrary set of rules, not your specific example), this is likely to be an undecidable problem. If the transforms are one way(i.e rules of the form $A \to BA$) it is so , for eg see: Tag System.