[Solved]: Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$

Problem Detail: 

I'm reading my textbook and it claims that the regular expression $c^*(b \cup (ac)^*)^*$ defines the language $L$ over $\{a,b,c\}$ which consists of all strings that do not contain the substring $bc$.

However, I'm failing to see how that language would contain strings such as $bbbaaa$ or $aaabbb$. Am I missing something or is that regular expression incorrect? The expression I come up with was $ \left( \left( \left( a \cup b \right) ^*a \right) ^* \left( c \cup a \right) ^* \right) ^*b^* $

Asked By : user7461

Answered By : Hendrik Jan

I checked an older edition of Sudkamp, and it had the same example. Actually the expression is $c^*(b\cup ac^*)^*$, which has a different bracketing. Your $(ac)^*$ specifies strings of the form $acac\dots ac$, whereas Sudkamp has $ac^*$ which means strings like $acc\dots c$.

It follows the arguments of the answer by Raphael, but backwards. Any sequence of $c$'s is either at the beginning of the string, or else it cannot be preceeded by $b$ because there is an explicit $a$ in the expressing.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10857

3.2K people like this

 Download Related Notes/Documents