Find a regular expression for the language of all words over {a,b} that include ab or ba

Question

My original thought for this problem was

(a+b)b*(a*+b)(λab) + (b+a)a*(b*+a)(λba)

but the problem with this is that it can't generate

abaa

So i tried to rewrite it as

(a+b)a*+b*(a*+b)(λab) + (b+a)a*+b*(b*+a)(λba)

If anyone could offer me some guidance or a push in the right direction to finding this regular expression i'd be grateful, thanks in advance.

Answer 1

For the set of all words containing $ab$, we need a regular expression $A$ such that $$L(A)=\{ab, aab, bab, aba, abb, aaab, abab, \cdots\}.$$ That is, $ab$ may be followed and preceded by any finite length word made up of $a$ and $b$. So you could write $L(A)$ as the following concatenation: $$L(A)=\{\lambda, a, b, aa, ab, ba, bb, \cdots\}\{ab\}\{\lambda, a, b, aa, ab, ba, bb, \cdots\}=L(a+b)^*L(ab)L(a+b)^*.$$ Therefore $A=(a+b)^*ab(a+b)^*$. Similar process would give regex for $ba$ and then you find the complete regex.

Answer 2

If a word starts with $a$, then it is in $L$ if it contains a $b$. Likewise, if a words starts with $b$, then it is in $L$ if it contains an $a$. Therefore a regular expression for $L$ is $(aa^*b + bb^*a)(a+b)^*$.