自动机只接受 ba^(n) for n>=1, odd n using 2 states
automata accepting only ba^(n) for n>=1, odd n using 2 states
我的考试有一道题要求用2 states ("O" and "E")画一个自动机，最终状态接受ba^(n)，for n>=1并且n必须是奇数。我花了 45 分钟，但我什至不认为我做对了。
你会怎么画呢？
我们可以用Myhill-Nerode来证明被请求是不可能的。我们可以说明等价性 classes w.r.t。这种语言的不可区分性关系。
考虑空字符串 e。它后面可以跟L中的任意字符串，得到L中的字符串。因此我们有一个等价的 class [e] 对应于自动机的初始状态。请注意，此状态不接受，因为 e 不是该语言中的字符串。
考虑字符串 a。这不能后跟任何字符串以得到L中的字符串，所以这是一个不同的等价class [a]。显然 a 不是该语言中的字符串，因此不接受。这不能与 [e] 对应的状态相同；实际上，对应于 [e] 的状态转换为对应于输入 a.
上的 [a] 的状态
我们现在有两个不同的非接受状态，它们必须出现在任何识别 L 的最小 DFA 中。由于 L 是非空的（留作练习），因此在任何最小 DFA 中都必须有一些其他接受状态。因此，存在接受 L 的非双态 DFA。 QED
继续分析，等价class是[e]、[a]、[b]和[ba]。转换 table 是：
q s q'
[e] a [a]
[e] b [b]
[a] a [a]
[a] b [a]
[b] a [ba]
[b] b [a]
[ba] a [b]
[ba] b [a]
只有[ba]对应的接受状态。
我的考试有一道题要求用2 states ("O" and "E")画一个自动机，最终状态接受ba^(n)，for n>=1并且n必须是奇数。我花了 45 分钟，但我什至不认为我做对了。
你会怎么画呢？
我们可以用Myhill-Nerode来证明被请求是不可能的。我们可以说明等价性 classes w.r.t。这种语言的不可区分性关系。
考虑空字符串 e。它后面可以跟L中的任意字符串，得到L中的字符串。因此我们有一个等价的 class [e] 对应于自动机的初始状态。请注意，此状态不接受，因为 e 不是该语言中的字符串。
考虑字符串 a。这不能后跟任何字符串以得到L中的字符串，所以这是一个不同的等价class [a]。显然 a 不是该语言中的字符串，因此不接受。这不能与 [e] 对应的状态相同；实际上，对应于 [e] 的状态转换为对应于输入 a.
[a] 的状态
我们现在有两个不同的非接受状态，它们必须出现在任何识别 L 的最小 DFA 中。由于 L 是非空的（留作练习），因此在任何最小 DFA 中都必须有一些其他接受状态。因此，存在接受 L 的非双态 DFA。 QED
继续分析，等价class是[e]、[a]、[b]和[ba]。转换 table 是：
q s q'
[e] a [a]
[e] b [b]
[a] a [a]
[a] b [a]
[b] a [ba]
[b] b [a]
[ba] a [b]
[ba] b [a]
只有[ba]对应的接受状态。