Question

Find a regular expression for the following language

L= {w∈{a,b}*:(na(w)-nb(w)mod)3=1}

please show explanation and steps

Answer 1

Here, we have given the Language as:-

L = {w {a,b}* : (na(w) – nb(w) mod)3 =1

The above language means that in a string we have to count the number of “a” and number of “b”, then take a difference between them and then divide it by 3, after dividing we should get a remainder as 1.

Or we can say that, the difference between the number of “a” and the number of “b” should be (multiple of 3 + 1), then only we can get remainder as 1.

For example:-

The regular expression should follow these values:

a =	b =	(a-b)|3 =
1	0	(1-0)|3 = 1
2	1	(2-1)|3 = 1
3	2	(3-2)|3 = 1
4	0	(4-0)|3 = 1
7	0,3	(7-0)|3 = 1 or (7-3)|3 = 1
10	0,3,7	(10-7)|3 = 1 or (10-3)|3 = 1 or (10 -0)|3 =1

Like that we can take the number of "a" and number of "b". And so on....

Now let’s consider the strings that will satisfy the above language.

Let’s take for "a" only:-

L = {λ, a, aaaa, aaaaaaa, aaaaaaaaaa, aaaaaaaaaaaaa,........}

If we take λ then, yes it can be accepted by the language as λ is constant. So we can get 1 as a remainder after dividing a constant by 3.

Next, we can take 4 times "a" as "aaaa". (Here number of "a" is 4 and number of "b" is 0, so we get 4 after subtracting 4-0 = 4 and when we divide 4 by 3 we will get 1 as a remainder.

similarly we can take 7 times "a" as "aaaaaaa" , then 9 times "a" and so on....Means if we take number of "a" as one more than the multiple of three then that string will be accepted by the language.

So, we can say that for “a” there is a cycle of 3 “a”.(Here, according to string we should take a cycle of 4 "a", but we will take a cycle of 3 only why? i will explain this later.)

So if we design a DFA for letter "a" only, our starting state will be q0 and the final state will be q1. So, if we start counting from q0 , then after moving one cycle the number of "a" which is multiple of 3 will come back to q0 and then we have to add one more "a" (as we have number of "a" one more than the multiple of 3)  so it moves to the final state q1.

Now, we will check for number of "b".

L = {a, aaaa, aaaaaaa, aaaaaaaaaa, aab, aaabb, aaaabbb, aaaaaaabbb, aaaaaaaaaabbb, aaaaaaaaaabbbbbb,.......}

So, if we take “b” as a multiple of three then it will be accepted by language. But in DFA we will take “b” as a reverse direction of “a” because we have to cancel “a” and “b” by subtracting and then divide it by 3 to get a remainder 1 which is lesser value than “a” and “b”.

Now our final DFA will be:-

Then, we will reduce the step to obtain the following NFA:-

Finally the regular expression is ((ba)* (a + bb) ) ((ab)* + (b + aa) (ba)* (a + bb))*.