Regular expression in theory of computation solved examples Part 4

Solution:

We have the input alphabets ∑ = {a, b}

Here, the resultant regular expression denote the set of all strings over ∑ in which the number of occurrence of ‘a’ is divisible by 3, i.e., the resultant regular expression will denotes the strings like aaab, baaaaaa, etc.

To fix this problem, first of all, let us find the languages denoted by-

                        a*        = {λ, a, aa, aaa, aaaa, aaaaa, .. .. .. .. ..}                       (1)
b*        = {λ, b, bb, bbb, bbbb, bbbbb, .. .. .. ..}                      (2)
ab*      = {a, ab, abb, abbb, abbbb, abbbbb, .. .. .. ..}             (3)
ba*      = {b, ba, baa, baaa, baaaa, baaaaa, .. .. .. .. ..}             (4)

From equation  (1), (2), (3) and (4), which is in first step, we have to find that in which language denoted by a particular regular expression, the number of occurrence of a varies.

Thus, after seeing carefully all the four regular expressions, we found that from equation (1), (2), (3), and (4), which is in first step, the number of occurrence of varies only in equation (1) and (4).

Thus, let us distinguish equation (1) an (4) as-

                        a*        = {λ, a, aa, aaa, aaaa, aaaaa, .. .. .. .. ..}                       (5)
ba*      = {b, ba, baa, baaa, baaaa, baaaaa, .. .. .. .. ..}             (6)

Now, we can formally write equation (5) and (6) in the following mathematically form-

                        a_i*        = {λ, a, aa, aaa, aaaa, aaaaa, .. .. .. .. ..}                       (7)
| where, i = 0, 1, 2, 3, 4, .. .. ….
ba_i*      = {b, ba, baa, baaa, baaaa, baaaaa, .. .. .. .. ..}             (8)
| where, i = 0, 1, 2, 3, 4, .. .. ….
Now, we can break the regular expression of equation (7) into the following two parts-

Part 1: Which contains such number of a’s which is not divisible by 3, and let us denote it by a1_i*, | where, i = 1, 2, 4, 5, 7, 8 .. .. .. .. and soon.
Part 2: Which contains such number of a’s which is divisible by 3, and let us denote it by a2_i*, | where, i = 0, 3, 6, 9, 12, .. .. .. .. and soon.

Similarly, we can break the regular expression of equation (8) into the following two parts are as follows-
Part 3: Which contains such number of a’s which is not divisible by 3, and let us denote it by ba1_i*, | where, i = 1, 2, 4, 5, 7, 8 .. .. .. .. and soon.

Part 4: Which contains such number of a’s which is divisible by 3, and let us denote it by ba2_i*, | where, i = 0, 3, 6, 9, 12, .. .. .. .. and soon
Now, we can get the regular expression in which the number of occurrence of a’s is not divisible by 3. It is-

                        a1_i* + ba1_i*

                        | where, i = 1, 2, 4, 5, 7, 8 .. .. .. .. and soon.

Now, we can also get the regular expression in which the number of occurrences of a’s is divisible by 3. It is-

                        a2_i* + ba2_i*

                        | where, i = 0, 3, 6, 9, 12, .. .. .. .. and soon

Thus the resultant regular expression over input alphabets ∑= {a, b} in which the number of occurrences of a’s is divisible by 3 can be given by-

                        (a1 + ba1)_i* (a2 + ba2)_i* (a1 + ba1)_i*

This is the resultant regular expression.

You can also Read: Context Free Grammar (CFG) Definition, Notation and Examples