A Regular Expression for all strings that...

Question

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with:

1. An even number of a's.
2. A 4k + 1 number of b's.
3. The length is divisible by 3.

The only solution that I could think of is:

1. $(b^*c^*ab^*c^*ab^*c^*)^*$

but I don't know if it's correct and I don't even know how to start for 2 and 3.... Also, I want to know, are the answers for these questions simples?, because I suspect that what they were asking me were examples of RE that met the conditions... and not make a RE that consider all possible strings that meet those conditions.

If is not as complex as I think... can you help me?

Answer 1

Your answer to 1 is almost correct: It does not accept strings with zero $a$s such as $bc$. And it does not accept for example $acba$. Try something like $$ [bc]^*(a[bc]^*a[bc]^*)^*$$ Based on this, you should have littel problems to find a regex for $4k$ number of $b$s and then $4k+1$ number of $b$s

For the third task, first solve "length equals $3$", then star

Answer 2

Question. What are the common features of your three problems?

Answer. You have to count some parameter modulo $n$ for a certain $n$.

For (1), you have to count $|u|_a$ modulo 2, for (2), you have to count $|u|_b$ modulo 4 and for (3) you have to count $|u|$ modulo 3. If you have this in mind, you can easily design a DFA for each situation. I will explain a generic case. Suppose you want a DFA for the language $$ L = \{u \in \{a, b, c\}^* \mid 3|u|_a + 2|u|_b - |u|_c \equiv 2 \pmod 5\} $$ The states of the DFA will be $\{0, 1, 2, 3, 4\}$: they correspond to the possible values of the sum $f(u) = 3|u|_a + 2|u|_b - |u|_c$ modulo $5$. The initial state is $0$, since if you take for $u$ the empty word, then $f(u) = 0$. The final state is $2$ since you want $f(u) \equiv 2 \pmod 5$.

Now to compute the transitions, you have to wonder what happens if you add an $a$, a $b$ or a $c$ to a word $u$. Well, it is not difficult to see that, modulo $5$, you get $$ f(ua) \equiv f(u) + 3 \quad f(ub) \equiv f(u) + 2 \quad f(uc) \equiv f(u) - 1 $$ And this gives you the transitions! For every state $q$, you get $$ q\cdot a = q + 3 \pmod 5 \quad q\cdot b = q + 2 \pmod 5 \quad q\cdot c = q -1 \pmod 5 $$ Now that you have a DFA, you can apply standard algorithms to convert it to a regular expression.