DFA将接受具有奇数1和奇数0的字符串

Question

我想要DFA生成，它将接受奇数为1和奇数为0的字符串。

Answer 1

首先，让我们构建一个接受奇数为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定理背后的直觉以及常规语言交叉的笛卡尔积机构造。

Answer 2

意味着你想要DFA为odd-odd language

这是你需要DFA的

看看这里当你申请0它不接受..然后你应用1它将达到最终状态。由于DFA接受奇数'0's和奇数'1's.it将接受字符串，除非它们的长度是奇数。你可以在DFA上运行字符串来检查它。希望它会对你有所帮助