4

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.

royhowie
  • 11,075
  • 14
  • 50
  • 67
user2804857
  • 41
  • 1

3 Answers3

2

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 (Na(x) = 1) and y = aabaa (Nb(y) = 1).

Or w = bbbabbba as x = bbbabb (Na(x) = 1) and y = ba (Nb(y) = 1)

Or w = baabaab as x = baa and y = baab with (Na(x) = 2) and (Nb(y) = 2).

So you can always break a string consist of a and b into prefix x and suffix y such that Na(x) = (Nb(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.

1And 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)*.

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
0

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.

Zane
  • 926
  • 8
  • 21
  • (1) First question is not about "how to proof whether a language regular"? it is about a particular problem. (2) `maybe think about why the set is not regular.` wrong to proof that certain language is not regular we have pumping lemma property of regular langue but proofing a language is regular is quite confusing because it is necessary but not sufficient condition. – Grijesh Chauhan Sep 28 '13 at 08:48
0

Hint: A = {a, b}*.

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

Joni
  • 108,737
  • 14
  • 143
  • 193