(* Regex for language with no words conatining "baba" as a substring: *)
ε+a+(ε+a)(a*)+((b+(ε+a)((a*)(b)))((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(a+(a)(a*)))+(((b+(ε+a)((a*)(b)))((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b)))(((((b)((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b)))*)(((b)((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(a+(a)(a*)))))+b+(ε+a)((a*)(b))+(b+(ε+a)((a*)(b)))(b*)+((b+(ε+a)((a*)(b)))((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)((a)((a*)(b))+((a)((a*)(b)))(b*)))+(((b+(ε+a)((a*)(b)))((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b)))(((((b)((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b)))*)(b+(b)(b*)+((b)((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)((a)((a*)(b))+((a)((a*)(b)))(b*)))))+(b+(ε+a)((a*)(b)))((b*)(a))+((b+(ε+a)((a*)(b)))((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(ε+((a)((a*)(b)))((b*)(a))))+(((b+(ε+a)((a*)(b)))((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b)))(((((b)((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b)))*)((b)((b*)(a))+((b)((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(ε+((a)((a*)(b)))((b*)(a))))))+((b+(ε+a)((a*)(b)))((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b))+(((b+(ε+a)((a*)(b)))((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b)))(((((b)((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b)))*)(ε+((b)((b*)(a)))(((((a)((a*)(b)))((b*)(a)))*)(b))))