# 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.

• How would you do it in a programming language? Oct 17, 2017 at 0:09
• Like in the Java we have regex function to analysis data. Like (a-z)*.{3.} Oct 17, 2017 at 0:24

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.