Geek Answers Handbook

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

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

A = {xy | N a (x) = N b (y)}

I find it difficult to determine where to start solving this problem. Any information would be greatly appreciated.

+4
source share
3 answers

Yes, this is a common language!

Any line consists if a and b belong to the language A = {xy | N a (x) = N b (y)} A = {xy | N a (x) = N b (y)} .

Example:
Suppose the line: w = aaaab we can split this line into the prefix x and the suffix y

  w = a aaab --- ----- xy

The number a in x is equal to one, and the number b in in y also equal.

Similarly, as a string like: abaabaa can be split 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).

Thus, you can always break the string from a and b into the prefix x and the suffix y so that N a (x) = (N b (y).

Formal Prrof:

Note. Strings consisting only of a or consisting of b do not belong to the language, for example. aa , a , bbb ...

Defines a new Lagrangian CA such that CA = {xy | N a (x) != N b (y)} CA = {xy | N a (x) != N b (y)} . CA means complement to a consists of a string consisting of only a or only b s.

1 And CA is a regular language whose regular expression is a + + b + .

Now that we know that CA is a regular language (it can be a regular expression, which means DFA) and the complement of any regular language is regular, a also a regular language!

To create DFAs for add-ons, refer to: Looking for a DFA Add-on? and for writing a regular expression for DFA, see the following two methods.

'+' Operator in regular expression in official languages

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

+2
source

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

Second: think about why dialing is not regular.

0
source

Hint: A = {a, b} *.

Try to prove this by induction on the length of the word or by finding the shortest word not in A.

0
source

More articles:


All Articles