复合有限自动机(FA)
原文:https://www.geeksforgeeks.org/compound-finite-automata-fa/
先决条件–有限自动机(FA) 复合 FA 是在给定的 d FA D1 和 D2 上执行操作(∩、∩、-)后形成的合成 DFA。
D1 = (Q1, ∑, δ, q1, F1) and D2 = (Q2, ∑, δ, q2, F2)
其中， Q 1 和 Q 2 :分别为 DFA D1 和 D2 的有限状态集合。 ∞:输入字母表包含有限数量的输入符号。 δ:过渡函数(δ:Qx∑- > Q) q 1 和 q 2 :分别为 D1 和 D2 的初始状态。 F 1 和 F 2 :分别为 DFA D1 和 D2 的最终状态集合。
复合有限自动机(FA)的性质:
- 化合物 FA (D1XD2)中的州数等于 m*n，其中 m 是 D1 的州数，n 是 D2 的州数。
- 复合 FA 的初始状态是 D1 和 D2 初始状态的组合。
- 复合 FA 的最终状态取决于所执行的操作。
示例:
D1 = no. of a's divisible by 2
D2 = no. of b's divisible by 3
D1 ({q1, B}, {a, b}, δ, q1, {q1}),
D1 ({q2, A, C}, {a, b}, δ, q2, {q2})
为以下内容构建最小 FA:
(D1∪D2),
(D1∩D2),
(D1-D2),
(D2-D1)
说明:
DFA D1:
DFA D2:
1。联合(D1∪D2): 任何属于 D1 语言或 D2 语言的字符串 w 都被合成复合自动机接受。 最终状态:如果 D1 的最终状态或 D2 的最终状态包含在复合 FA 的任何状态中。
2。交集(D1∪D2): 属于 D1 语言和 D2 语言的任何字符串都被合成复合自动机接受。 最终状态:如果 D1 的最终状态和 D2 的最终状态都包含在复合 FA 的任何状态中。
3。差异(D1-D2): D1 接受的任何字符串，而不是 D2 接受的字符串。 最终状态:如果 D1 的最终状态和 D2 的非最终状态包含在复合 FA 的任何状态中。
4。差异(D2-D1): D2 接受的任何字符串，而不是 D1 接受的字符串。 最终状态:如果 D2 的最终状态和 D1 的非最终状态包含在复合 FA 的任何状态中。
版权属于：月萌API www.moonapi.com，转载请注明出处
