[Math] A Regular Expression for all strings that…

automataformal-languagesregular expressionsregular-language

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?

Best Answer

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