Writing regular expressions

Question

So here's the problem: Let $Σ =\{a, b, c\}$. Write a regular expression for the set of all strings in $Σ^∗$ such that the sum of the number of $a$’s and $b$’s in the string is at most two. Thus the string can have an $a$ and a $b$ but cannot have two $a$’s and a $b$, for example.

And here's what I've come up with: $(a \cup b) \cup c^*$. This way, it's not possible to have more than two $a$'s and $b$'s in the string. Did I solve the problem correctly? Thank you!

Answer 1

A simple way is to split into cases:

• At most 0 $a$ or $b$: $c^*$
• At most 1 $a$ or $b$: $c^* (a \mid b) c^*$
• At most 2 $a$ or $b$: $c^* (a \mid b) c^* (a \mid b) c^*$

The union of the three cases gives what you want.

Another way is to write $c^* (a \mid b \mid \epsilon) c^* (a \mid b \mid \epsilon) c^*$ (there are two $a$, $b$, or nothing in a sea of $c$s).