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

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

我推荐你读哥德尔、埃舍尔、巴赫=）它准确地讨论了你在这里所描述的内容。

总之，提出的一个解决方案是找到系统的不变量：如果该属性在操作开始时为真，则在所有情况下在操作结束时也必须为真。

如果您的第一个字符串具有该不变性，而您的结束字符串不具有该不变性，那么您的替换规则将永远不会生成第二个字符串。

你的不变规则可以更强大......例如，它可以是一种当且仅当的关系（当且仅当第一步为真时，最后一步的不变式才为真），所以你可以证明如果第一个字符串中存在不正确的不变量，则结束字符串不可到达。请注意，这些当且仅当关系自动遵循标准 if 关系，如果您的所有规则都是双向的（您可以向后和向前应用它们）

例如，以下是您的第一个系统中可能存在的不变量：

• 所有不包含连续字符串组合“cat”或“dog”的连续字符串也必须出现在最终状态

给定不变规则，很容易提供一个决策公式来决定给定起始字符串是否可能出现字符串。

附加

我希望你不介意我采用霍夫施塔特的术语，即：

• 给定的起始字符串将被称为“公理”
• 公理可以通过一组规则来执行
• 任何字母串都称为“定理”；可以通过给定公理的规则产生的一串字母称为“有效定理”

所以，你的问题从“X能产生Y吗？” 到“Y 是一个有效的定理，可以从 X 导出吗？”

因此，让我们从更一般的角度来解决您的字符串替换问题。我们将称为A所有替换字符串的有序集，以及A所有替换字符串的有序集。因此，这里我们有一个通用规则：

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

这就是说，“如果我们看到一个定理，其中有一个集合 中的字符串，被字符串和A包围，那么我们也可以推导出， ，其中是相应的替换字符串。xyxB[n]yB[n]

让我们找到一些不变量，无论集合A和B中的内容如何，​​它们都是正确的。

• 由于替换字符串的长度始终与其替换字符串相同，因此公理中未在 in 中找到的任何字母都A不得移动

例如，如果我们有 axiomabcdea和 Ruleset A=["cd",de"]，很容易看出字母 a 和 b 在 中找不到A。因此，我们可以说该系统中的所有定理都必须具有以下形式ab##a。这给了我们一个规则来寻找不存在的东西定理的

然而，对于很长的集合A，这可能对我们没有多大帮助，因为A可能会使用所有字母。

让我们尝试让它变得更有用......

• 公理末尾的任何字母（不在 中字符串末尾的字母A）都不能移动。对于位于公理开头但不在 中字符串开头的任何字母也可以这样说A。

假设我们有A=["dog","cat","ton"]，any 如果公理以除 g、t 或 c 以外的任何字母结尾，则所有可推导的定理也必须以同一字母结尾。如果公理以 d、c 或 t 之外的任何字母开头，则所有可导出的定理也必须以相同的字母开头。

这在某种程度上更有用，因为对于任何A大小 < 26 的字母，您将得到它们不以结尾或开头的字母。然而，你的公理以这些特定字母开头或结尾的可能性就大大降低了。

然而，我们发现我们可以进一步扩展：

• 公理开头的任何连续字母串，如果不是字符串 in 开头的连续字符串，A则不得移动；对于公理末尾的连续字符串，它不是 中字符串末尾的连续字符串，也是如此A。

我们会发现这更有用！ A必须至少有 26^n 个元素大，我们才能认为这个不变量无用。

现在，请注意，我们也可以倒退！也就是说，我们可以说：

• 理论开头的任何连续字母串，如果不是 in 字符串开头的连续字符串，B也必须存在于所有公理中；对于定理末尾的连续字符串，它不是 中字符串末尾的连续字符串，也是如此B。

根据这些规则，我组装了一个决策树，用于确定哪些案例已锁定，哪些案例无法确定。您会注意到，我们只有两个这样的无法确定的情况。

现在剩下的就是找到这两种情况的不变量。不过，我们可以注意到一件事：

• 不变规则 toCASE 2也可以应用于CASE 1，忽略前导/尾随“not-in-A/B”字符串

也就是说，如果您有A=["cat","dog"],B=["dog","cut"], 和公理定理boabcdut boablmut，那么您可以应用于 的任何不变规则CASE 2也可以应用于cdut => mlut，并且具有不匹配的前导字符串boab。这大大简化了事情。

所以，我们基本上已经将两种未确定的情况解决为一种情况；让我们看看还能分析什么...

...下一次。我稍后会回到这个话题。