# Identify the set of strings of odd length over {a, b} that contain the substring bb

I need identify the set of possible strings of odd length over $\sum$ (the alphabet) {a, b} that contain the substring bb.

This is new material and a new concept to me and would really appreciate any perspective on how to go about solving this (with an explanation of course).

The only ways I see possible of solving this is through a mathematical proof by induction approach? Or by generating a regular-expression that defines this language (which is also something I feel is a bit ambiguous).

• A regular expression unambiguously defines a language. – Q the Platypus Sep 20 '16 at 4:02
• Yes of course; I am saying that the process of generating a regular expression that defines a language is not clear to me. – taylor.tackett Sep 20 '16 at 4:11

HINT: You could start by finding a regular expression for the strings that contain the substring $bb$, irrespective of their length: the simplest is

$$(a+b)^*bb(a+b)^*\;.\tag{1}$$

Each of the subexpressions $(a+b)^*$ matches the set of all strings over $\{a,b\}$, so $(1)$ matches anything of the form $ubbv$ with $u,v\in\Sigma^*$, i.e., any string that has the substring $bb$ in it somewhere.

But we want only the strings $ubbv$ of odd length. Now $|uv|=|ubbv|-2$, so $ubbv$ has odd length if and only if $uv$ has odd length. And $|uv|=|u|+|v|$, so we want to generate all pairs of strings $u$ and $v$ such that $|u|+|v|$ is odd. That happens precisely when one of $|u|$ and $|v|$ is odd and the other is even.

• Explain why the regular expression $$(aa+ab+ba+bb)^*\tag{2}$$ matches precisely the strings over $\Sigma$ that have even length.

• Find a regular expression that matches precisely the strings over $\Sigma$ that have odd length; you may find it helpful to start with $(2)$ and modify or add to it.

• Use the previous results to get a regular expression that matches precisely the words $ubbv\in\Sigma^*$ such that $|u|$ is odd and $|v|$ is even.

• Do the same for words $ubbv$ such that $|u|$ is even and $|v|$ is odd.

Now put the pieces together to get a regular expression that matches precisely those words over $\Sigma$ that contain the substring $bb$ and have odd length.

• Thank you for the detailed explanation. Just so I am sure, are we guaranteeing ubbv will have odd length by stating the cardinality of |uv| = the cardinality of |ubbv| - 2? And in regards to your definition of the regular expression that matches strings that have even length; is the reason because no matter what, whenever we enter into that 'kleene star' we will always be grabbing strings of length 2 (resulting in all evens)? – taylor.tackett Sep 20 '16 at 6:58
• Also, when you define (1), would I be correct in saying the '+' can also be thought of as the union of a and b? – taylor.tackett Sep 20 '16 at 7:16
• @taylor.tackett: To answer the last question first: There are several variants of regular set notation; I’ve seen $\cup$, $\lor$, and $\mid$ used where I used $+$. Whichever symbol is used, I think of it as or: $a+b$ matches $a$ or $b$. This isn’t precisely a union, but it’s the same idea, so you’re probably interpreting the $+$ correctly. – Brian M. Scott Sep 20 '16 at 17:57
• @taylor.tackett: We want $ubbv$ to have odd length. Because $|ubbv|=|uv|+2$, $|ubbv|$ and $|uv|$ are either both odd or both even. Thus, ensuring that $uv$ has odd length is exactly what’s needed to ensure that $ubbv$ has odd length. \\ Yes, since each of $aa,ab,ba$, and $bb$ has even length, concatenating any number of them via the star results in a string of even length. The other important point here is that every string of even length is a concatenation of these four substrings: just chop it up into pairs, and each pair must be one of these four things, because no other pairs exist. – Brian M. Scott Sep 20 '16 at 18:01

A regular expression to generate strings of odd lengths:

         (a+b)+a|b(aa+ab+ba+bb)*