regular-language - 证明以下在 {a,b} 上的集合是正则的

Question

给定字母表 {a, b}我们定义 Na(w)作为 a 的出现次数在字w和 Nb(w) 类似.显示以下集过{a, b}是定期的。

A = {xy | Na(x) = Nb(y)}

我很难弄清楚从哪里开始解决这个问题。任何信息将不胜感激。

Answer 1

是的，这是常规语言!

任何字符串都包含 if a和 b所属语言 A = {xy | Na(x) = Nb(y)} .

示例:
假设字符串是:w = aaaab我们可以将这个字符串分成前缀 x和后缀 y

  w =   a     aaab
       ---   -----
        x      y

a数量在 x是 1，b 的数量在y也是其中之一。

与字符串类似:abaabaa可以破为 x = ab (Na(x) = 1) 和 y = aabaa (Nb(y) = 1)。

或 w = bbbabbba如 x = bbbabb (Na(x) = 1) 和 y = ba (铌(y) = 1)

或 w = baabaab x = baa和 y = baab与 (Na(x) = 2) 和 (Nb(y) = 2)。

所以你总是可以打破由 a 组成的字符串和 b成前缀 x和后缀 y使得 Na(x) = (Nb(y))。

正式教授:

注意:一个字符串只包含 a s 或由 b 组成s 不属于 languagr 例如aa , a , bbb ...

让我们定义新的拉格朗日 CA使得 CA = {xy | Na(x) != Nb(y)} . CA代表 A 的补码由字符串组成 仅由 a 组成s 或仅 b s。

1而CA是一种正则语言，它的正则表达式是a+ + b+ .

现在我们知道 CA 是一种正则语言(它可以通过正则表达式和 DFA 表达)并且任何正则语言的补码都是正则因此语言 A也是普通话!

为补语构建 DFA 引用:Finding the complement of a DFA?并为 DFA 编写正则表达式引用以下两种技术。

How to write regular expression for a DFA

How to write regular expression for a DFA using Arden theorem

'+' Operator in Regular Expression in formal languages

PS:顺便说一句 A = {xy | Na(x) = Nb(y)} 的正则表达式是 (a + b)*a(a + b)*b(a + b)* .