patternMinor
Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$
Viewed 0 times
theallcontainsubstringcupthatdefinedoesstringsover
Problem
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^* $
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^* $
Solution
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.
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.
Context
StackExchange Computer Science Q#10857, answer score: 7
Revisions (0)
No revisions yet.