Regular Expression even length at least aaaa-substring

Question

I need to build a regular expression that defines a language containing all even length with at least an aaaa-substituting in them. I think this - ((ba) + (ab) + (bb) + (aa))* aaaa ((ba) + (ab) + (bb) + (aa))* works but im wondering if there is a way to simplify this?

Answer 1

It doesn’t quite work: you don’t get $baaaab$, for instance. Your expression covers all of the words $xa^4y$ such that $|x|$ and $|y|$ are even, but it misses the words $xa^4y$ with $|x|$ and $|y|$ both odd.

Suppose that $xaaaay$ is in the language, and $|x|$ and $|y|$ are odd. If $x=x'a$, then $xaaaay=x'\color{red}{aaaa}ay$ has a block of $aaaa$ between strings of even length, so it’s generated by your expression. The same is true if $y=ay'$. Thus, the only problematic case is when $x=x'b$ and $y=by'$, in which case $xaaaay=x'baaaaby'$ has the string $baaaab$ between two strings of even length.

I don’t know whether you consider it a simplification, but you can rewrite

$$aa+ab+ba+bb$$

as $\big((a+b)(a+b)\big)^*$. Call this expression $\sigma$. Then we’ve just shown that

$$\sigma(aaaa+baaaab)\sigma$$

covers all of the desired language.

Answer 2

The one simplification I can think of is to replace ((ba)+(ab)+(bb)+(aa))* with ((a+b)(a+b))*.

Additionally, your expression doesn't take into account words like baaaab where the only instances of aaaa are sandwiched between two odd-length strings.
This can be remedied by using ((a+b)(a+b))* (aaaa+baaaab)((a+b)(a+b))*, for instance.