From what I understand the regular expression (a* + b*) . (a.b)* accepts the following strings:
Empty string, aaaaaaaaaababab, bbbbbbbbbbabab, aabab, babab, etc with different lengths of a, b and ab.
Do I have it right?
From what I understand the regular expression (a* + b*) . (a.b)* accepts the following strings:
Empty string, aaaaaaaaaababab, bbbbbbbbbbabab, aabab, babab, etc with different lengths of a, b and ab.
Do I have it right?
Yes. $a^*+b^*$ gets you all strings that do not contain both $a$ and $b$, so you get the strings $a^n$ and $b^n$ for $n\ge 0$. $(ab)^*$ gets you $(ab)^n$ for all $n\ge 0$. Thus, $(a^*+b^*)(ab)^*$ gives you the strings $a^m(ab)^m$ and $b^n(ab)^m$ for $m,n\ge 0$.
The easiest way to check a string $w$ is to start processing it from the back. Find the maximum word $u$ of the form $(ab)^n$ that is a final segment of $w$: $u=(ab)^n$ for some $n\ge 0$, and $w=xu$ for some $x$. If $x$ has the form $a^*$ or $b^*$, then $w$ matches $(a^*+b^*)(ab)^*$; if not, it doesn’t.