字母替换终止
Letter substitutions termination
给定：
- A char string
S length l containing only characters from 'a' to 'z'
- A set of
ordered substitution rules R (in the form X->Y) where x, y are single letters from 'a' to 'z' (eg, 'a' -> ' e' could be a valid rule but 'ce'->'abc' would never be a valid rule)
当 R 中的规则 r 应用于 S 时，S 的所有字母等于规则的 left side r 将被替换为 r 的 right side 中的字母，如果规则 r 导致 S 中的任何替换，则 r 被称为 triggered rule.
流程图（算法）：
(1) 在S.
上交替应用R中的all规则（按照R中规则的顺序）
(2) while (there exists any 'triggered rule' DURING (1) ) : 重复 (1)
(3) 终止
问题是：有没有办法确定给定字符串 S 和集合 R，算法是否会终止（运行 永远）
示例 1：（手动执行）
S = 'abcdef' R = { 'a'->'b' , 'b' -> 'c' }
(the order is implied the order of appearance from left to right of each rule)
S 和 R 上的 运行 算法：
(1.1): 'abcdef' --> 'bbcdef' --> 'cccdef'
(2.1): 重复 (1) 因为 (1.1)
期间有 2 次替换
(1.2): 'cccdef'
(2.2): 继续(3)因为在(1.2)
期间没有更换
(3) : 终止算法
=> 算法终止于给定的 S 和 R
示例 2：
S = 'abcdef' R = { 'a'->'b' , 'b' -> 'a' }
(the order is implied the appearance order from left to right of each rule)
S 和 R 上的 运行 算法：
(1.1): 'abcdef' --> 'bbcdef' --> 'abcdef'
(2.1): 重复 (1) 因为 (1.1)
期间有 2 次替换
(1.2): 'abcdef --> 'bbcdef' --> 'abcdef'
(2.2): 重复 (1) 因为 (1.2)
期间有 2 次替换
(1.3): ......永远与 (1.1) 相似......
永远不会到达步骤 (3)（终止）。
=> 算法不会以给定的 S 和 R 终止。
- 我对此进行了研究，但没有找到解决该问题的有效算法
"if the algorithm halts"。
我想到的第一个想法是 "find cycle" 个字母
在 triggered rules 中，但规则数量可能过多
为了这个想法是理想的。
第二个是提出一个"threshold"的时间
重复，如果超过阈值，我们结束算法
不会终止。
"threshold"可以随机选择，（只要大
够了）- 这种方法并不是很引人注目。
我在想，如果有 upper bound
"threshold" 这确保我们总能得到正确的答案。
我想出了 threshold = 26 其中 26 是
从 'a' 到 'z' 的信 - 但我无法证明它是真的（或不是）。
（我希望它会像 Bellman-Ford 算法那样以固定步数确定负循环，..）
你呢？请帮我找到答案（这不是
作业）
感谢您的阅读。
考虑解决这个问题的一种简单方法是考虑一个长度为 1 的字符串，看看问题是否可以针对任何给定的起始字母循环。由于字符串的长度永远不会改变，并且应用规则独立地应用于 S 中的每个字符，因此只考虑长度为 1 的字符串就足够了。
现在，从具有 26 个状态的状态图开始 - 每个字母对应 1 个状态。现在，对于您的状态转换，请考虑以下过程：
一次按顺序从 R 1 应用转换，直到到达 R 的末尾。如果从特定状态（字母）开始，您永远不会到达新字母，您知道如果到达起始字母，你终止。否则，在应用 R 的 entire 序列后，您将得到一个新字母。这将是你的新状态。
请注意，所有状态转换都是确定性的，因为我们应用了 R 的整个序列，而不仅仅是单个转换。如果我们应用单独的转换，我们可能会感到困惑，因为我们可能有 a -> b、b->a、a->c。在查看单个操作时，我们可能认为从 a 有两种可能的转换（到 b 或到 c），但实际上，考虑到整个序列，我们明确地看到 a 到 c 的转换。
在考虑每个起始字母的下一个状态后，您将完成状态图的创建。以这种方式创建整个状态图需要 26 * |R|操作。如果状态图包含一个循环，那么如果字符串S包含循环中的任意一个字母，则停止失败，否则停止。
或者，如果您只是考虑在对来自 R 的整个序列进行 26 次迭代后停止，您也可以使用它。
给定：
- A char string
Slengthlcontaining only characters from'a'to'z'- A set of
orderedsubstitution rulesR(in the formX->Y) wherex,yare single letters from'a' to 'z'(eg,'a' -> ' e'could be a valid rule but'ce'->'abc'would never be a valid rule)
当 R 中的规则 r 应用于 S 时，S 的所有字母等于规则的 left side r 将被替换为 r 的 right side 中的字母，如果规则 r 导致 S 中的任何替换，则 r 被称为 triggered rule.
流程图（算法）：
(1) 在S.
上交替应用R中的all规则（按照R中规则的顺序）
(2) while (there exists any 'triggered rule' DURING (1) ) : 重复 (1)
(3) 终止
问题是：有没有办法确定给定字符串 S 和集合 R，算法是否会终止（运行 永远）
示例 1：（手动执行）
S =
'abcdef'R ={ 'a'->'b' , 'b' -> 'c' }
(the order is implied the order of appearance from left to right of each rule)
S 和 R 上的 运行 算法：
(1.1): 'abcdef' --> 'bbcdef' --> 'cccdef'
(2.1): 重复 (1) 因为 (1.1)
期间有 2 次替换
(1.2): 'cccdef'
(2.2): 继续(3)因为在(1.2)
期间没有更换
(3) : 终止算法
=> 算法终止于给定的 S 和 R
示例 2：
S =
'abcdef'R ={ 'a'->'b' , 'b' -> 'a' }
(the order is implied the appearance order from left to right of each rule)
S 和 R 上的 运行 算法：
(1.1): 'abcdef' --> 'bbcdef' --> 'abcdef'
(2.1): 重复 (1) 因为 (1.1)
期间有 2 次替换
(1.2): 'abcdef --> 'bbcdef' --> 'abcdef'
(2.2): 重复 (1) 因为 (1.2)
期间有 2 次替换
(1.3): ......永远与 (1.1) 相似......
永远不会到达步骤 (3)（终止）。
=> 算法不会以给定的 S 和 R 终止。
- 我对此进行了研究，但没有找到解决该问题的有效算法 "if the algorithm halts"。
我想到的第一个想法是
"find cycle"个字母 在triggered rules中，但规则数量可能过多 为了这个想法是理想的。第二个是提出一个
"threshold"的时间 重复，如果超过阈值，我们结束算法 不会终止。"threshold"可以随机选择，（只要大 够了）- 这种方法并不是很引人注目。我在想，如果有
upper bound"threshold"这确保我们总能得到正确的答案。 我想出了threshold = 26其中 26 是 从 'a' 到 'z' 的信 - 但我无法证明它是真的（或不是）。 （我希望它会像 Bellman-Ford 算法那样以固定步数确定负循环，..）你呢？请帮我找到答案（这不是 作业）
感谢您的阅读。
考虑解决这个问题的一种简单方法是考虑一个长度为 1 的字符串，看看问题是否可以针对任何给定的起始字母循环。由于字符串的长度永远不会改变，并且应用规则独立地应用于 S 中的每个字符，因此只考虑长度为 1 的字符串就足够了。
现在，从具有 26 个状态的状态图开始 - 每个字母对应 1 个状态。现在，对于您的状态转换，请考虑以下过程：
一次按顺序从 R 1 应用转换，直到到达 R 的末尾。如果从特定状态（字母）开始，您永远不会到达新字母，您知道如果到达起始字母，你终止。否则，在应用 R 的 entire 序列后，您将得到一个新字母。这将是你的新状态。
请注意，所有状态转换都是确定性的，因为我们应用了 R 的整个序列，而不仅仅是单个转换。如果我们应用单独的转换，我们可能会感到困惑，因为我们可能有 a -> b、b->a、a->c。在查看单个操作时，我们可能认为从 a 有两种可能的转换（到 b 或到 c），但实际上，考虑到整个序列，我们明确地看到 a 到 c 的转换。
在考虑每个起始字母的下一个状态后，您将完成状态图的创建。以这种方式创建整个状态图需要 26 * |R|操作。如果状态图包含一个循环，那么如果字符串S包含循环中的任意一个字母，则停止失败，否则停止。
或者，如果您只是考虑在对来自 R 的整个序列进行 26 次迭代后停止，您也可以使用它。