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).

  • 1
    $\begingroup$ A regular expression unambiguously defines a language. $\endgroup$ – Q the Platypus Sep 20 '16 at 4:02
  • $\begingroup$ Yes of course; I am saying that the process of generating a regular expression that defines a language is not clear to me. $\endgroup$ – 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


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.

  • $\begingroup$ 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)? $\endgroup$ – taylor.tackett Sep 20 '16 at 6:58
  • $\begingroup$ Also, when you define (1), would I be correct in saying the '+' can also be thought of as the union of a and b? $\endgroup$ – taylor.tackett Sep 20 '16 at 7:16
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Sep 20 '16 at 17:57
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Sep 20 '16 at 18:01

A regular expression to generate strings of odd lengths:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.