3
$\begingroup$

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^* $

|cite|improve this question
$\endgroup$
  • $\begingroup$ Did the textbook say $bbbaaa$ is in $L$? $\endgroup$ – scaaahu Mar 28 '13 at 4:08
  • $\begingroup$ @scaaahu Not directly, but it says $L$ contains all strings which don't contain $bc$ as a substring, so $bbbaaa$ fits the criteria. $\endgroup$ – user7461 Mar 28 '13 at 4:10
  • 1
    $\begingroup$ I concur, another very simple example is $a$, certainly doesn't contain $bc$, but there's no possible way to generate only $a$s in the expression. You expression looks okay to me, I got $(a\cup c\cup b^{+}a)^{\ast}b^{\ast}$ from the DFA->Regex conversion. $\endgroup$ – Luke Mathieson Mar 28 '13 at 5:35
  • $\begingroup$ I'm always a little cautious when I think there's a mistake in a textbook, it's usually me doing something stupid. The book is An Introduction to the Theory of Computer Science, Languages and Machines by Thomas Sudkamp. Example 2.3.10. $\endgroup$ – user7461 Mar 28 '13 at 6:30
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for clearing it up. $ac^*$ is definitely different from $(ac)^*$. $\endgroup$ – scaaahu Mar 30 '13 at 3:49
4
$\begingroup$

Here is how you can make sure there is a mistake in the book:

  1. Use the algorithm from the book to transform the regular expression into an NFA.
  2. Optional: determinise the automaton, using the algorithm from the book.
  3. Run your example through the automaton and note whether it accepts.

Provided you followed the conversion algorithm correctly and the word is not accepted, there is a mistake in the book: either the claim you quote is wrong or one of the algorithms is wrong.

Spoilers: as mentioned in the comments, the regular expression does not describe the claimed language. The author's epxression enforces "every $a$ is followed by a $c$", which is stronger than the claim.

Your expression looks quite complicated. All you need to do is ensure that every $b$ is followed by $a$, $b$ or the end of the word!

$(b^*a \mid c )^*b^*$

You can also build a suitable automaton -- basically, start with one that accepts everything and modify it to move to a dead state upon reading $bc$ -- and convert it to a regular expression. Perform whatever construction you can more easily prove correct.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The "make regular expression out of automaton" algorithms give abominations of regular expressions... $\endgroup$ – vonbrand Mar 28 '13 at 12:21
  • 1
    $\begingroup$ @vonbrand But they are provably correct, which may be more interesting than conciseness. And, of course, algorithms can be implemented but "see, understand and solve" can not. $\endgroup$ – Raphael♦ Mar 28 '13 at 21:22

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.