如何检测文本替换是否导致无限循环？
How to detect if text replacement results in an infinite loop?
我开发了一个从其他程序中提取文本的程序。其中一个特点是用户可以指定"replacement scripts"来处理文本。替换脚本示例：
|ORIG|a|BECOMES|bb|END|
|ORIG|b|BECOMES|cc|END|
替换过程搜索任何 ORIG 文本并将其替换为相应的 BECOMES 文本。因此，如果提取文本 aaaa，它将首先替换为 bbbbbbbb，然后替换为 cccccccccccccccc。
当有这样的替换脚本时，问题就出现了：
|ORIG|a|BECOMES|bb|END|
|ORIG|b|BECOMES|aa|END|
并且在提取的文本中有一个a。 a 变成 bb 变成 aaaa 变成 bbbbbbbb 等等直到无穷大。
因此我需要两个算法：
1. 阅读替换脚本并检测它是否可能创建无限循环（这样我就可以警告用户）。
2. 执行替换脚本时检测死循环（所以我可以中止操作并通知用户）。
我不知道从哪里开始。我已经考虑了两个多星期，但一无所获。
如果第一个脚本的 ORIG 是第二个脚本的 BECOMES 的一部分，您可以尝试构建一个图表，其中的节点代表您的替换脚本，边连接一个脚本与另一个脚本。
然后你可以在这个图中搜索循环，告诉你你可以无限期地应用这个循环中的规则。
如果任何 ORIG 等于或任何 BECOMES 的子串，那么您可能会遇到问题。
如评论中所述，我的替换脚本实际上是图灵完备的。这样问题就变成了停机问题，无法解决。
我开发了一个从其他程序中提取文本的程序。其中一个特点是用户可以指定"replacement scripts"来处理文本。替换脚本示例：
|ORIG|a|BECOMES|bb|END|
|ORIG|b|BECOMES|cc|END|
替换过程搜索任何 ORIG 文本并将其替换为相应的 BECOMES 文本。因此，如果提取文本 aaaa，它将首先替换为 bbbbbbbb，然后替换为 cccccccccccccccc。
当有这样的替换脚本时，问题就出现了：
|ORIG|a|BECOMES|bb|END|
|ORIG|b|BECOMES|aa|END|
并且在提取的文本中有一个a。 a 变成 bb 变成 aaaa 变成 bbbbbbbb 等等直到无穷大。
因此我需要两个算法： 1. 阅读替换脚本并检测它是否可能创建无限循环（这样我就可以警告用户）。 2. 执行替换脚本时检测死循环（所以我可以中止操作并通知用户）。
我不知道从哪里开始。我已经考虑了两个多星期，但一无所获。
如果第一个脚本的 ORIG 是第二个脚本的 BECOMES 的一部分，您可以尝试构建一个图表，其中的节点代表您的替换脚本，边连接一个脚本与另一个脚本。
然后你可以在这个图中搜索循环，告诉你你可以无限期地应用这个循环中的规则。
如果任何 ORIG 等于或任何 BECOMES 的子串，那么您可能会遇到问题。
如评论中所述，我的替换脚本实际上是图灵完备的。这样问题就变成了停机问题，无法解决。