Lets say that I have the following regular expression for binary strings: $$ S = \{0\}^*\bigl(\{1\}\{1\}^*\{0\}\{0\}^* \setminus \{11\}\{11\}^*\{0\}\{00\}^*\bigr)^*\{1\}^* $$ My understanding is that the above is the unambiguous expression for all binary strings which do not have an even block of ones followed by an odd block of ones.

If I want to find the generating series for this string, is it OK to subtract the generating series of $\{11\}\{11\}^*\{0\}\{00\}^*$ from $\{1\}\{1\}^*\{0\}\{0\}^*$?



Browse other questions tagged or ask your own question.