4

给定字母表{a, b}，我们将其定义为单词中出现的次数，对于. 证明下面的集合是有规律的。Na(w)awNb(w){a, b}

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

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

4

3 回答 3

2

是的，它是普通语言！

任何字符串都由 ifa和b属于 language组成。A = {xy | Na(x) = Nb(y)}

例子：
假设字符串是：w = aaaab我们可以把这个字符串分为前缀x和后缀y

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

ain的数量x 是一，bin 的数量y也是一。

与字符串类似：abaabaa可以分解为x = ab(N a (x) = 1) 和y = aabaa(N b (y) = 1)。

或w = bbbabbba如x = bbbabb(N a (x) = 1) 和y = ba(N b (y) = 1)

或者w = baabaab作为 x =baa 和y = baab(N a (x) = 2) 和 (N b (y) = 2)。

因此，您始终可以将由a和组成的字符串分解b为前缀x和后缀y，使得 N a (x) = (N b (y).

正式教授：

注意：字符串仅a由 s 组成或由bs 组成不属于 languagr 例如aa, a, bbb...

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

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

现在我们知道 CA 是一种正则语言（它可以是正则表达式等 DFA 表达式），任何正则语言的补码都是正则语言，因此语言A也是正则语言！

要为补语构建 DFA，请参阅：找到 DFA 的补语？并为 DFA 编写正则表达式参考以下两种技术。

  1. 如何为 DFA 编写正则表达式
  2. 如何使用 Arden 定理为 DFA 编写正则表达式

正式语言正则表达式中的“+”运算符

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

于 2013-09-28T08:37:57.507 回答
0

首先，找出如何证明一个集合是正则的。一种方法是定义一个接受该语言的有限状态机。

第二：也许想想为什么集合不规则。

于 2013-09-22T18:41:09.977 回答
0

提示：A = {a, b}*。

尝试通过对单词长度的归纳来证明它，或者通过找到不在A 中的最短单词来证明它。

于 2013-09-22T18:55:47.693 回答