是否可以在此重写系统中得出字符串？

Question

重写系统是$ a leftrightarrow b $的形式的一组规则。如果我们将该规则应用于字符串$ w $，我们将用$ b $的$ w $中的任何子字符串$ a $ a $ a $ a $，反之亦然。

给定一个启动字符串$ aaabb $，我们可以在系统中使用以下规则得出$ baab $：

• $ a leftrightarrow ba $
• $ baba leftrightarrow aabb $
• $ aaa leftrightarrow ab $
• $ ba leftrightarrow ab $

有一般算法吗？

Answer 1

请注意，$ a $ s的均等数不会改变。由于一个字符串包含一个奇数$ a $，而另一个字符串也无法达到。

我相信（对于一套任意的规则，而不是您的具体示例），这可能是一个不确定的问题。如果转换是一种方式（即表单$ a to ba $的规则），则是这样，例如，请参见： 标签系统.