Show that the following set over {a,b} is regular

问题:

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 | Na(x) = Nb(y)}

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

回答1:

Yes it is regular language!

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

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

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

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

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

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

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

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).

Formal Prrof:

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

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.

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

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!

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. How to write regular expression for a DFA
2. How to write regular expression for a DFA using Arden theorem

'+' Operator in Regular Expression in formal languages

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

回答2:

First, find out how to prove that a set is regular. One way is to define a finite state machine that accepts the language.

Second: maybe think about why the set is not regular.

回答3:

Hint: A = {a, b}*.

Try proving it by induction on length of word, or by finding the shortest word not in A.