证明对{a，b}的以下设置是常规的 [英] Show that the following set over {a,b} is regular

问题描述

鉴于字母 {a，b} 我们定义了 N a （w）作为单词 w 中 a 的出现次数，对于 N b （w）。证明在 {a，b} 上的以下设置是常规的。

Given the alphabet {a, b} we define Na(w) as the number of occurrences of a in the word w and similarly for Nb(w). Show that the following set over {a, b} is regular.

A = {xy | N a （x）= N b （y）}

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

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

I'm having a hard time figuring out where to start solving this problem. Any information would be greatly appreciated.

推荐答案

是的，它是常规语言！

Yes it is regular language!

如果 a 和 b 属于语言 A = {xy | N a （x）= N b （y）} 。

Any string consists if a and b belongs the language A = {xy | Na(x) = Nb(y)}.

示例：

假设字符串为： w = aaaab 我们可以将此字符串分为前缀 x 和后缀 y

Example:
Suppose string is: w = aaaab we can divide this string into prefix x and suffix y

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

x 中 a 的个数为1，而<$ y 中的c $ c> b 也是一个。

Number of a in x is one, and number of b in in y is also one.

类似字符串像： abaabaa 可以被破坏为 x = ab （N _a （x）= 1）和 y = aabaa （N _b （y）= 1）。

Similarly as string like: abaabaa can be broken as x = ab (N_a(x) = 1) and y = aabaa (N_b(y) = 1).

或 w = bbbabbba 如 x = bbbabb （ N _a （x）= 1）和 y = ba （N _b （y）= 1）

Or w = bbbabbba as x = bbbabb (N_a(x) = 1) and y = ba (N_b(y) = 1)

或 w = baabaab ，因为x = baa 和 y = baab ，其中（N _a （x）= 2）和（N _b （y）= 2）。

Or w = baabaab as x = baa and y = baab with (N_a(x) = 2) and (N_b(y) = 2).

因此，您始终可以中断由 a 和 b 放入前缀 x 并后缀 y 使得N a （x）= （N b （y）。

So you can always break a string consist of a and b into prefix x and suffix y such that N_a(x) = (N_b(y).

正式价格：

注意：字符串仅包含 a s或包含 b s不属于languagr例如 aa ， a ， bbb ...

Note: A strings consists of only as or consist of bs doesn't belongs to languagr e.g. aa, a, bbb...

让我们定义新的Lagrange CA 使得 CA = {xy | N a （x）！= N b （y）} 。 CA 表示<$ c的补码$ c> A 由字符串组成，仅由 a s或仅由 b s组成。

Lets defined new Lagrange CA such that CA = {xy | Na(x) != Nb(y)}. CA stands for complement of A consists of string consists of only as or only bs.

¹ 并且CA是一种正则语言，它的正则表达式是 a + + b + 。

¹And CA is a regular language it's regular expression is a+ + b+.

现在，我们知道CA是一种正则语言（可以通过正则表达式来表达，因此DFA），任何常规语言的补语都是常规h ence语言 A 也是常规语言！

Now as we know CA is a regular language (it can be expression by regular expression and so DFA) and Complement of any regular language is Regular hence language A is also regular language!

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

To construct DFA for complement language refer: Finding the complement of a DFA? and to write regular expression for DFA refer following two techniques.

1. 如何为DFA写正则表达式


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

1. How to write regular expression for a DFA
2. How to write regular expression for a DFA using Arden theorem

' +'正式语言中的正则表达式

PS： A的Btw正则表达式= xy | N a （x）= N b （y）} 是（a + b）* a（a + b）* b（a + b）* 。

PS: Btw regular expression for A = {xy | Na(x) = Nb(y)} is (a + b)*a(a + b)*b(a + b)*.

这篇关于证明对{a，b}的以下设置是常规的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！