计算理论门 2012
Theory of computation GATE 2012
4) 考虑{0,1}上的字符串集合，其中每个3个符号的子字符串最多有两个零。例如，001110 和 011001 在该语言中，但 100010 不是。所有长度小于 3 的字符串也在该语言中。接受此语言的部分完成的 DFA 如下所示。
DFA 中缺失的弧是
我正在为明年的 GATE 做准备，这就是为什么我选择了 GATE 问题，所以关于这个问题的任何帮助都将是 appreciated.Thank 你！
答案为选项(D)。
首先从不能有三个连续 0 的语言开始。因此，00 状态的 0 输入必须进入死状态 (q)。它仅在选项 (C) 和 (D) 中定义。现在，我们只剩下两个选择了。现在你看到状态 10。在选项 (C) 0 输入到状态 10 它只进入 10，它是循环和任何数字 0 到 10 它只停留在 10 并且 10 也是最终状态所以它接受任何没有的语言连续的 0，它一定不会发生。所以现在我们留下选项 (D) 和 (D) 0 输入到 10 它进入状态 00 再一个 0 到 00 它进入死状态所以它不会接受三个连续的 0 并且它会做我们的语言want.and 你的 DFA 应该喜欢这个。
这只在选项 (D) 中完成。抱歉我的英语不好。
4) 考虑{0,1}上的字符串集合，其中每个3个符号的子字符串最多有两个零。例如，001110 和 011001 在该语言中，但 100010 不是。所有长度小于 3 的字符串也在该语言中。接受此语言的部分完成的 DFA 如下所示。
DFA 中缺失的弧是
我正在为明年的 GATE 做准备，这就是为什么我选择了 GATE 问题，所以关于这个问题的任何帮助都将是 appreciated.Thank 你！
答案为选项(D)。 首先从不能有三个连续 0 的语言开始。因此，00 状态的 0 输入必须进入死状态 (q)。它仅在选项 (C) 和 (D) 中定义。现在，我们只剩下两个选择了。现在你看到状态 10。在选项 (C) 0 输入到状态 10 它只进入 10，它是循环和任何数字 0 到 10 它只停留在 10 并且 10 也是最终状态所以它接受任何没有的语言连续的 0，它一定不会发生。所以现在我们留下选项 (D) 和 (D) 0 输入到 10 它进入状态 00 再一个 0 到 00 它进入死状态所以它不会接受三个连续的 0 并且它会做我们的语言want.and 你的 DFA 应该喜欢这个。
这只在选项 (D) 中完成。抱歉我的英语不好。