Q:

Find a regular expression of following sets

The set of strings over $\{a, b, c\}$ with length greater than three.
The set of strings over $\{a, b\}$ where every $a$ is immediately preceded and followed by $b$.
The set of strings over $\{a, b\}$ that do not end with $ba$.
I understand how to do it in the programming language, but I think I have to use math language to explain it. Such as $(a+b)^*abc(a+b)^*...$
Could someone please give me a hand? Thanks so much.

A:

For the first one:
$$(a+b+c)^* / ((a+b+c)^3 \cup (a+b+c)^2 \cup (a+b+c))$$
$(a+b+c)^*$ means a substring consisting of any number of $a$, $b$, or $c$ and any combination thereof including ones of length $0$, $/$ means the complement ($A/B$ means elements found in $A$ but not $B$), and the remaining terms, the power denotes length (so $(a+b+c)^k$ means substrings within the alphabet of length $k$).
In short, it means all strings within the alphabet of all lengths except those of length $3$, $2$, or $1$.
For the second one:
$$(a+b)^*(bab)(a+b)^*$$
$(a+b)^*$ means a substring consisting of any number of $a$, $b$ or combination thereof including ones of length $0$, $bab$ means a substring of an $a$ preceded and followed by a $b$. So strings in this set include:
$$bab, abab, aabab, ..., bbab, abbab, ..., baba, babaa, ...$$
Think of it as all strings containing $bab$ with any number of characters before or after. This conforms to the requirements stated.

