创建具有奇 0 奇偶校验的确定性有限自动机 - 结合 DFA
Creating a Deterministic Finite Automata with Odd 0 Parity - Combining DFA
我已经在这个项目上工作了将近一个星期，但老实说这超出了我的理解，我在其他地方找不到帮助。
我现在的问题是，我不知道如何组合 FSA。据我了解，我必须结合我的 2 个 FSA，即主 FSA 和奇数 0 奇偶校验 FSA。
这是主要的 FSA：
这是奇 0 奇偶校验 FSA：
我已经对这个项目困惑了将近一个星期了，它已经到期了，所以提交它已经太晚了，但我仍然坚持下去，我真的很想结束它。
还有谁能解释一下为什么这个表达式不起作用？ （拒绝 0100）
((00100|00011|010)(00100|00011|010))*0|((00100|00011|010)(00100|00011|010))*(00100|00011|010)1
好的，这是我的想法 jason 很好地指出了你会遇到的问题，首先我会用我的代码创建一个 table，并创建一组可以接受的字符串
A = 00100
B = 00011
c = 010
和一组 acceptable 根据您的指导方针的字符串将是
000110
001000100001110
给你的字母编码表达式
001000 不会被偶数 0 奇偶校验 属性 接受 table。请注意，这只是一个 A，因此不会接受 A 或 C 消息。我鼓励您重做您的字母代码，一个 3 位数的代码会更容易，因为您将拥有更大的接受字符串集，而您的 DFA 可能会更小。
给出你的代码，很难实现一个只有 DFA 的解决方案，或者一个简单的只有 DFA 的解决方案。还要记住，字母之间的代码不应该是其他代码的前缀，这将简化您的问题。
假设我们的代码是
A = 101
B = 001
C = 110
然后我们有以下一组 acceptable 消息，偶数 0 对 属性:
1010
1011010
1100
0011100
请注意，在人类语言中，您会有一定数量的 A 后跟 0，任意数量的 BC 后跟 0，依此类推。您可以从那里开始形成您的正则表达式。我希望这已经足够清楚了。
我不知道像这样合并 FSA 的一般方法，但这是针对您的特定问题的方法。
将原始 FSA 复制两份，分别命名为 'Even' 和 'Odd'。不变的是，无论何时您处于其中一个子 FSA 的状态，奇偶校验都如其名称所示。为此，每个 0 转换必须跳转到另一个 FSA 中的相应节点； 1 转换在同一个 FSA 中继续。
起始状态为偶数。 Odd对应节点不可达，可以删除
您所有的原始接受状态都不再有效，因为您还没有验证奇偶校验位。在 Odd 中，每个状态都需要 1 转换到新的接受状态。在 Even 中，来自前一个接受状态的 0 需要是一个接受状态；所有这些转换都已经存在，因此它们的目标（节点 #1）成为新的接受状态。
至于为什么您的正则表达式解决方案不起作用，请考虑其中的第一个子组：(00100|00011|010)。这包括具有偶数和奇数 0 的子模式；您无法判断哪一个匹配，因此您已经永远忘记了最终的奇偶校验是什么。您必须以某种方式安排整个正则表达式的每个单独部分以仅匹配具有相同奇偶校验的事物 - 我不完全确定这在传统正则表达式中是否可行。 （如果我使用正则表达式的现代计算机实现来解决这个问题，我会使用先行断言来验证整体奇偶校验，作为一个完全独立的过程，与验证三种模式的串联无关。）
编辑：插图！
我们首先制作您的原始 FSA 的两份副本，标记为偶数或奇数校验。您也可以将此视为为第一个 FSA 中的每个节点制作第二个 FSA 中的节点副本。
起始状态为 Even，因为您最初有零个 0。状态 o0 是不可到达的，在以后的图中将被省略。标签还无效，因为每次有 0 转换时，奇偶校验都会改变——这些转换需要转到 FSA 的另一个副本。对于所有这些交叉，我无法让 graphviz 生成任何稍微可以理解的东西，所以我将不得不删除 even/odd 状态周围的框。这是应用交叉的图表：
这个 FSA 与你原来的句子完全相同，除了你总是知道你在每个状态下是否有奇偶校验。接受状态仍然与原始状态相同：为了处理您的最终奇偶校验位，我们需要添加一个从每个状态到新接受状态的最终转换。从所有三个 Odd 接受状态，有一个 1 转换到标记为 "o" 的新状态。在所有四个 Even 接受状态中，最终的奇偶校验位将是一个 0 转换——恰好对应于现有的 "o1" 状态。这是最终图，其中包含更新的接受状态：
您想要的是一个 DFA，它接受两种语言的所谓 交集：
- 语言 (00100 + 00011 + 010)*(0+1)
- 奇数个0的字符串语言
(注：我加(0+1)代表你要加到最后的位，如果不是这个意思，请无视。
我针对如何以这种方式组合 DFA 的问题发布了一个经过充分审查的答案：请参阅 here。简要总结：
- 为您的两种语言创建 DFA M1 和 M2
- 创建一个新的 DFA M3，如下所示：
- Q3 = Q1 x Q2（M3 的状态是 M1 和 M2 的有序状态对）
- S3 = (S1, S2)（初始状态为M1,M2的有序初始状态对）
- A3 = {(q1, q2) | A1 中的 q1，A2 中的 q2}（接受状态是有序的状态对，其中两个元素都在各自的机器中接受状态。这给你交集。对于联合，至少一个必须接受。对于差异，q1 必须接受和q2一定不能。等)
- f3 : Q3 x E -> Q3 定义为 f3((q1, q2)) = (q1', q2') 其中 f1(q1) = q1' 和 f2(q2) = q2'。
在您的例子中，您将获得一个 DFA，其状态数是第一个 DFA 的两倍。该 DFA 的第一个 "copy" 表示偶校验，第二个 "copy" 表示奇校验。您的机器将像以前一样工作，但只要您看到 0，就会在 "copies" 之间来回跳转。只有奇校验副本会保持其接受状态。
我已经在这个项目上工作了将近一个星期，但老实说这超出了我的理解，我在其他地方找不到帮助。
我现在的问题是，我不知道如何组合 FSA。据我了解，我必须结合我的 2 个 FSA，即主 FSA 和奇数 0 奇偶校验 FSA。
这是主要的 FSA：
这是奇 0 奇偶校验 FSA：
我已经对这个项目困惑了将近一个星期了，它已经到期了，所以提交它已经太晚了，但我仍然坚持下去，我真的很想结束它。
还有谁能解释一下为什么这个表达式不起作用？ （拒绝 0100）
((00100|00011|010)(00100|00011|010))*0|((00100|00011|010)(00100|00011|010))*(00100|00011|010)1
好的，这是我的想法 jason 很好地指出了你会遇到的问题，首先我会用我的代码创建一个 table，并创建一组可以接受的字符串
A = 00100
B = 00011
c = 010
和一组 acceptable 根据您的指导方针的字符串将是 000110 001000100001110
给你的字母编码表达式 001000 不会被偶数 0 奇偶校验 属性 接受 table。请注意，这只是一个 A，因此不会接受 A 或 C 消息。我鼓励您重做您的字母代码，一个 3 位数的代码会更容易，因为您将拥有更大的接受字符串集，而您的 DFA 可能会更小。
给出你的代码，很难实现一个只有 DFA 的解决方案，或者一个简单的只有 DFA 的解决方案。还要记住，字母之间的代码不应该是其他代码的前缀，这将简化您的问题。
假设我们的代码是
A = 101
B = 001
C = 110
然后我们有以下一组 acceptable 消息，偶数 0 对 属性:
1010
1011010
1100
0011100
请注意，在人类语言中，您会有一定数量的 A 后跟 0，任意数量的 BC 后跟 0，依此类推。您可以从那里开始形成您的正则表达式。我希望这已经足够清楚了。
我不知道像这样合并 FSA 的一般方法，但这是针对您的特定问题的方法。
将原始 FSA 复制两份，分别命名为 'Even' 和 'Odd'。不变的是，无论何时您处于其中一个子 FSA 的状态，奇偶校验都如其名称所示。为此，每个 0 转换必须跳转到另一个 FSA 中的相应节点； 1 转换在同一个 FSA 中继续。
起始状态为偶数。 Odd对应节点不可达，可以删除
您所有的原始接受状态都不再有效，因为您还没有验证奇偶校验位。在 Odd 中，每个状态都需要 1 转换到新的接受状态。在 Even 中，来自前一个接受状态的 0 需要是一个接受状态；所有这些转换都已经存在，因此它们的目标（节点 #1）成为新的接受状态。
至于为什么您的正则表达式解决方案不起作用，请考虑其中的第一个子组：(00100|00011|010)。这包括具有偶数和奇数 0 的子模式；您无法判断哪一个匹配，因此您已经永远忘记了最终的奇偶校验是什么。您必须以某种方式安排整个正则表达式的每个单独部分以仅匹配具有相同奇偶校验的事物 - 我不完全确定这在传统正则表达式中是否可行。 （如果我使用正则表达式的现代计算机实现来解决这个问题，我会使用先行断言来验证整体奇偶校验，作为一个完全独立的过程，与验证三种模式的串联无关。）
编辑：插图！
我们首先制作您的原始 FSA 的两份副本，标记为偶数或奇数校验。您也可以将此视为为第一个 FSA 中的每个节点制作第二个 FSA 中的节点副本。
0 转换时，奇偶校验都会改变——这些转换需要转到 FSA 的另一个副本。对于所有这些交叉，我无法让 graphviz 生成任何稍微可以理解的东西，所以我将不得不删除 even/odd 状态周围的框。这是应用交叉的图表：
1 转换到标记为 "o" 的新状态。在所有四个 Even 接受状态中，最终的奇偶校验位将是一个 0 转换——恰好对应于现有的 "o1" 状态。这是最终图，其中包含更新的接受状态：
您想要的是一个 DFA，它接受两种语言的所谓 交集：
- 语言 (00100 + 00011 + 010)*(0+1)
- 奇数个0的字符串语言
(注：我加(0+1)代表你要加到最后的位，如果不是这个意思，请无视。
我针对如何以这种方式组合 DFA 的问题发布了一个经过充分审查的答案：请参阅 here。简要总结：
- 为您的两种语言创建 DFA M1 和 M2
- 创建一个新的 DFA M3，如下所示：
- Q3 = Q1 x Q2（M3 的状态是 M1 和 M2 的有序状态对）
- S3 = (S1, S2)（初始状态为M1,M2的有序初始状态对）
- A3 = {(q1, q2) | A1 中的 q1，A2 中的 q2}（接受状态是有序的状态对，其中两个元素都在各自的机器中接受状态。这给你交集。对于联合，至少一个必须接受。对于差异，q1 必须接受和q2一定不能。等)
- f3 : Q3 x E -> Q3 定义为 f3((q1, q2)) = (q1', q2') 其中 f1(q1) = q1' 和 f2(q2) = q2'。
在您的例子中，您将获得一个 DFA，其状态数是第一个 DFA 的两倍。该 DFA 的第一个 "copy" 表示偶校验，第二个 "copy" 表示奇校验。您的机器将像以前一样工作，但只要您看到 0，就会在 "copies" 之间来回跳转。只有奇校验副本会保持其接受状态。