Est-il possible de dériver une chaîne dans ce système de réécriture?

Question

système Réécriture est un ensemble de règles sous forme de $ A \ B leftrightarrow $. Si l'on applique cette règle à une chaîne $ w $ nous remplaçons une sous-chaîne $ A $ en $ $ w avec une sous-chaîne $ B $ et vice versa.

d'une chaîne à partir $ AAABB $ peut-on déduire $ BAAB $ dans le système avec les règles suivantes:

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

Y at-il un algorithme général pour cela?

Answer 1

Notez que la parité du nombre de $ A $ s ne change pas. Depuis une chaîne contient un nombre impair $ A $ et l'autre même, ils ne sont pas accessibles.

Je crois en général (pour un ensemble arbitraire de règles, pas votre exemple spécifique), cela est susceptible d'être un problème indécidable. Si les transformations sont d'une façon (ie règles de la forme $ A \ à BA $), il est ainsi, par exemple, voir: Tag système .