DFA 中的互补过程
原文:https://www . geesforgeks . org/complexing-process-in-DFA/
先决条件–设计有限自动机
假设我们有一个由(Q、
、
、q0、F)定义的 DFA，它接受语言 L 1 。那么，接受语言 L 2 的 DFA，其中 L 2 = ̅L 1 ，定义如下:
( Q, , , q0, Q-F )
DFA 的补码可以通过使非最终状态成为最终状态来获得，反之亦然。补语 DFA L 2 所接受的语言是 L 1 语言的补语。
示例-1: L 1 :偶数长度{a，b}上的所有弦的集合
L1 = {, ab, aa, abaa, aaba, ....}
L 2 :奇数长度{a，b}的所有弦的集合
L2 = { a, b, aab, aaa, bba, bbb, ...}
在这里，我们可以看到 L 2 = ̅L 1
让我们首先绘制接受偶数长度字符串的 L 1 的 DFA。
现在，为了设计 L 2 的 DFA，我们只需要补充上面的 DFA。我们将把非最终状态更改为最终状态，将最终状态更改为非最终状态。
这是我们必需的补充 DFA。
示例-2: L 1 :以‘a’开头的{a，b}上所有字符串的集合。
L1 ={ a, ab, aa, aba, aaa, aab, ..}
L 2 :不以‘a’开头的{a，b}上所有字符串的集合。
L2 ={ , b, ba, bb, bab, baa, bba, ...}
在这里，我们可以看到 L 2 = ̅L 1
让我们首先绘制 L 1 的 DFA，它接受{a，b}上以“a”开头的所有字符串的集合
现在，为了设计 L 2 的 DFA，我们只需要补充上面的 DFA。我们将把非最终状态更改为最终状态，将最终状态更改为非最终状态。
这是我们必需的补充 DFA，它接受不以“a”开头的字符串。 注:常规语言在补语下闭合(即常规语言的补语也将是常规的)。
版权属于：月萌API www.moonapi.com，转载请注明出处
