computer-science - 是否有两个状态 TG 接受来自 {a, b}* 的所有输入字符串，这些字符串不在 EVEN-EVEN 中？

Question

我对有限自动机和转移图这个话题很陌生。我有一个测验，询问是否有一个两态 TG 接受来自 {a,b}* 的所有字符串，这些字符串不在 EVEN-EVEN 中（具有偶数个 a 和偶数个 b 的语言）。请解释这是否可能。

标签： computer-scienceautomatacomputation-theoryfinite-automataautomata-theory

Answer 1

我们可以使用 Myhill-Nerode 定理来证明这种语言不存在两态确定性有限自动机。我们可以开始按字典顺序递增检查字符串，看看每个字符串是否可以与之前的字符串区分开来。如果我们找到三个可相互区分的字符串，我们就完成了。

空字符串是第一个，并且与它之前的所有其他字符串完全不同（无）。我们可以将此 q0 及其等价类 [e] 称为最小 DFA 中的状态。此状态不接受，因为空字符串是偶数/偶数。在此之后得到一个不在偶数/偶数中的字符串的字符串正是不在偶数/偶数中的字符串。

字符串 a 是下一个字符串，并且可以与空字符串区分开来，因为它的状态必须是接受。称其状态为 q1 及其等价类 [a]。在此之后可以到达非偶数/偶数的字符串的字符串是非奇数/偶数的字符串。

字符串 b 是下一个字符串，并且可以与其他两个字符串区分开来；可以跟随此以获得不在偶数/偶数中的字符串的字符串是不在偶数/奇数中的字符串。这意味着我们需要第三种状态，称为 q3，在该语言的最小 DFA 中。因此，最小 DFA 必须至少具有三个状态。

至于这种语言是否存在具有两种状态的 NFA（不是偶数/偶数）：可能没有。我们对决定论本身没有问题，而是我们必须记住多少。对于两种状态，我们只能记住到目前为止我们所看到的是否被接受。我们无法记住任何其他可以帮助我们前进的东西。aaabbb 和 abb 就我们的语言而言是可区分的，但不仅是 wrt 成员，因为 aaabbb 和 abb 都在该语言中。