给定字母表 {a, b}，我们将 N(w) 定义为 a 在单词 w 中出现的次数，N(w) 也是如此。证明以下对 {a, b} 的集合是正则的。
我很难弄清楚从哪里开始解决这个问题。任何信息将不胜感激。
最佳答案
是的，这是常规语言!
如果 a 和 b 属于语言 A = {xy | N(x) = N(y)} ，则任何字符串都包含。
示例:
假设字符串是:w = aaaab 我们可以将这个字符串分为前缀 x 和后缀 y
w = a aaab
--- -----
x y
a中x的个数为1，b中y的个数也为1。与字符串类似:
abaabaa 可以分解为 x = ab (Na(x) = 1) 和 y = aabaa (Nb(y) = 1)。或
w = bbbabbba 作为 x = bbbabb (Na(x) = 1) 和 y = ba (Nb(y) = 1)或
w = baabaab 为 x = baa 和 y = baab 与 (Na(x) = 2) 和 (Nb(y) = 2)。因此，您始终可以将包含
a 和 b 的字符串分解为前缀 x 和后缀 y，使得 Na(x) = (Nb(y))。正式类(class):
注意:一个字符串只包含
a s 或包含 b s 不属于 languagr 例如aa , a , bbb ...让我们定义新的拉格朗日
CA 使得 CA = {xy | N(x) != N(y)} 。 CA 代表 A 的补码，由仅包含 a 或仅包含 b 的字符串组成。1并且 CA 是一种正则语言，它的正则表达式是
a + b 。现在我们知道 CA 是一种正则语言(它可以通过正则表达式和 DFA 表达)并且任何正则语言的补码都是正则因此语言
A 也是正则语言!为补语构建 DFA 引用:Finding the complement of a DFA? 和为 DFA 编写正则表达式引用以下两种技术。
'+' Operator in Regular Expression in formal languages
PS: 顺便说一句，
A = {xy | N(x) = N(y)} 的正则表达式是 (a + b)*a(a + b)*b(a + b)* 。关于regular-language - 证明以下在 {a,b} 上的集合是正则的，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18947420/