algorithm - 检查字符串替换规则是否会生成另一个字符串

Question

不是家庭作业。
给定两个长度相同的字符串s和t。
给定一组替换规则，在s中找到子字符串a并用字符串b替换它。
A和B的长度相同。
是否有一系列规则应用程序，使字符串s变成字符串t？
例子：
我们有替换规则

cat->dog
dog->cut

我们有绳子
s1:awesomecat和s2:awesomecut
替换顺序可以是

awesomecat 
awesomedog cat->dog
awesomecut dog->cut

这是一个简单的例子，可能有这样的规则。

cat->dog
ate->dog
dog->cat

我相信没有比在每个州尝试每一条规则更好的方法来回答这个问题。这将是指数时间。但我不知道是否有更好的解决办法。

Answer 1

我建议您阅读Godel, Escher, Bach=）它讨论的正是您在这里描述的内容。
总之，一个建议的解决方案是找到一个invariant到您的系统：一个属性，如果在操作开始时是真的，那么在所有情况下在操作结束时也必须是真的。
如果第一个字符串具有该不变量，而结束字符串不具有该不变量，则替换规则将永远不会生成第二个字符串。
你的不变量规则可以更强大…例如，它可以是一个if和only if关系（不变量在最后一步是真的，前提是第一步是真的），因此你可以证明，如果第一个字符串中有一个不变量不是真的，那么结束字符串是不可到达的。请注意，如果您的所有规则都是双向的，则这些if和only if关系将自动遵循标准if关系（您可以前后应用它们）
例如，在第一个系统中有一个可能的不变量：
所有不包含连续字符串组合“cat”或“dog”的连续字符串也必须出现在结束状态
给定这个不变的规则，就可以直接提供一个决定公式来决定给定起始字符串时字符串是否可行。
追加
我希望你不介意我接受霍夫施塔特的条件，那就是：
给定的起始字符串将被称为“公理”。
公理可以由一组规则来作用。
任何一组字母都被称为“定理”；由给定公理的规则产生的一系列字母称为“有效定理”。
所以，你的问题从“x能产生y吗？”到“y是一个有效的定理，可以从x导出吗？”
所以，让我们从更一般的术语来处理字符串替换问题。我们将调用所有替换字符串的有序集，并调用所有替换字符串的有序集。因此，这里我们有一个单一的广义规则：

"xA[n]y" => "xB[n]y"

这意味着，“如果我们看到一个定理有一个字符串在集合A中，被字符串A和A包围，那么我们也可以导出x，其中y是相应的替换字符串。
让我们找到一些不变量，它们是真的，不管集合中有什么xB[n]y和B[n]。
由于替换字符串总是与它们替换的字符串相同，所以在A中找不到的公理中的任何字母都不能移动。
例如，如果我们有公理B和规则集A，很容易看出字母“a”和“b”在abcdea中没有找到。因此，我们可以说这个系统中的所有定理都必须是A=["cd",de"]形式的。这就给了我们一个规则来发现什么不是定理。
然而，对于很长的一组A，这可能帮不了我们多少忙，因为ab##a可能会用到所有的字母。
让我们试着让这个更有用…
在公理末尾的任何字母，不是在A中的字符串结尾，都不能移动。在公理开头的任何一个字母中都可以这样说，它不是在A中的字符串的开头。
假设我们有A，如果公理在任何不是g、t或c的字母中结束，所有可推导的定理也必须以同一个字母结束。如果公理以任何字母D、C或T开头，则所有可导定理也必须以相同的字母开头。
这有点更有用，因为对于任何A大小<26的字母，它们都不会以字母结尾或开头。然而，你的公理越来越不可能以这些特定的字母开头或结尾。
然而，我们发现我们可以进一步扩展：
在一个公理的开头，在A=["dog","cat","ton"]字符串的开头不是连续字符串的任何连续字符串都不能移动；在公理末尾的连续字符串相同，在A字符串中的结尾不是连续字符串。
我们会发现这更有用！A必须至少有26^n个元素大，我们才能将此不变量视为无用。
现在，注意，我们也可以倒退！也就是说，我们可以说：
在理论的开头，在A中的字符串的开头不是连续的字符串的任何连续字符串也必须存在于所有公理中；在定理的结尾处的连续字符串相同，这在A字符串中的结尾不是连续的字符串。
有了这些规则，我组装了一个decision tree来计算我们锁定了哪些案件，哪些案件是不确定的。你会注意到我们只有两个这样不确定的案子。
现在剩下的就是找到这两种情况的不变量。然而，我们可以注意到一件事：
B的不变规则也可以应用于B，忽略前导/尾随的“不在a/b”字符串
也就是说，如果你有CASE 2和公理定理CASE 1 A=["cat","dog"],B=["dog","cut"]，那么你可以应用到boabcdut的任何不变规则也可以应用到boablmut，不匹配的引导字符串CASE 2被忽略。这大大简化了事情。
所以，我们基本上解决了两个未定案件，一个案件，让我们看看还有什么可以分析…
…另一次。我一会儿再谈这个。