automata - 将接受具有奇数个 1 和奇数个 0 的字符串的 DFA
问题描述
我想要 DFA 生成,它将接受具有奇数个 1 和奇数个 0 的字符串。
解决方案
首先,让我们构建一个接受奇数 0 的 DFA。我们至少需要一个状态,否则我们不能接受任何东西。该状态不能接受,因为空字符串引导到那里并且空字符串没有奇数 0。因此,我们至少需要两个状态 - 一个不接受的初始状态和一个接受状态。我们需要更多吗?
为了回答这个问题,让我们开始填充过渡,看看我们得到了什么。必须有一个源自接受状态的转换。它去哪儿了?如果它转到自身,那么我们不接受字符串 0,它有一个奇数(一)为 0。所以我们需要在初始状态下进入 0 上的某个接受状态。我们恰好已经有一个接受状态;让我们去那里。
接下来,我们必须从接受状态转换。如果我们返回接受状态,我们将接受字符串 00,所以我们不能这样做。我们必须过渡到某种不接受的状态。我们已经有了一个不接受的状态——我们的初始状态——所以这个选择可能会起作用。或者,如果不是,我们必须引入一个新状态。让我们首先考虑返回初始状态是否有效,因为在这种情况下我们就完成了。
我们已经推断出字符串 0 和 00 被正确处理了。从那时起,000 将被正确处理,因为我们在随后的 0 上从初始状态返回到接受状态;实际上,我们在 0^2k 时返回初始状态,在 0^(2k+1) 时返回接受状态,因为 k >= 0。因此,这个 DFA 对于奇数为 0 的字符串的语言是正确的。图表看起来像:
/---0----\
| |
V |
----->(q0)--0-->(q1)
通过更改标签,我们可以获得奇数 1 字符串语言的自动机:
/---1----\
| |
V |
----->(q2)--1-->(q3)
为了让自动机接受包含奇数 0 和 1 的字符串,想象一下同时运行两个自动机:每当我们看到 0 时,我们将其传递给第一个,而每当我们看到 1 时,我们将其传递给第二个。然后,如果两个自动机最终都处于接受状态,我们就接受。我们可以通过将来自第一个和第二个自动机的所有四对状态视为一个新的组合自动机的状态来表示两个自动机的组合状态,其转移图如下所示:
/----0----\
| |
V |
----->(q0,q2)--0-->(q1,q2)
^ | ^ |
| 1 | 1
1 | 1 |
| V | V
(q0,q3)--0-->(q1,q3)
^ |
| |
\----0----/
这些是关于语言规则性的 Myhill-Nerode 定理和规则语言交集的笛卡尔积机器构造背后的直觉。
推荐阅读
- matlab - Matlab中逐行保存文本文件中数组数据的解决方法
- audio - 声音使应用程序在 Android 上滞后 - 有什么解决方案吗?
- android - 带有 Material Component 主题的 colorAccent 或 colorSecondary
- logic - 如何在精益中证明 r → (∃ x : α, r)
- reference - 借来的价值在循环中的寿命不够长
- c++ - 参数化构造函数的调用是如何执行的?
- python - 我可以创建一个跨文本小部件内多行的 Tkinter 画布吗?
- ruby - 如何在 RSpec 引发异常时测试输出到 stderr 的一段代码?
- python - Cython - 具有 numpy 属性的类
- game-maker - 斜坡上的对角线移动 | 游戏制作者 2