I'm trying to be ahead of the game by studying some Theory of Computation concepts before class starts at the end of this month. There's this question I came across that I don't understand below.

Let L be the language defined by the regular expression:
(c U ab U b)*bb(c U ab)

(U = union)

A.  Write 10 distinct strings that belong to L.  
    If such strings don't exist, explain why.

B.  Write 10 distinct strings over alphabet {a,b,c} that don't belong to L.  
    If such strings don't exist, explain why.

I'm totally lost, I have the answer but I just don't get how to go about it.

The only answers that I've came up with, that belong to L, was:

bbc, bbab

Which's only 2 correct out of the 10 listed in the answer key. I just can't see how to come about the rest of them.

Thanks for taking the time to read.

  • 1
    $\begingroup$ Do you understand regular expression notation? Why don't you use the part before bb to generate more strings? $\endgroup$
    – adrianN
    Commented Jan 5, 2017 at 14:01
  • $\begingroup$ @adrianN Thanks for your response. Here are some of the answers I came up with, since it says distinct strings. Tell me if they could be right: 3. cabb 4. cccccab 5. cababca 6. abcbbb 7. ccbabb 8. abbcb $\endgroup$
    – chompy
    Commented Jan 5, 2017 at 14:08

1 Answer 1


Let's break down the regular expression $(c \cup ab \cup b)^*bb(c \cup ab)$. It has three parts $(c \cup ab \cup b)^*$, $bb$, and $(c \cup ab)$. The first part means "zero or more repetitions of $(c \cup ab \cup b)$", the second part matches two $b$, and the third part matches $c$ or $ab$.

As you already mentioned in your question bbc and bbab are strings that are matched. In both we choose zero repetition of the first part then the obligatory bb and then c, respectively ab, to match the third part. To make this easier to see I'll separate the parts of the string that are matched by the different parts of the expression with a - like so: -bb-c and -bb-ab.

We can generate more strings by choosing more than zero repetitions of the first part. For example we can choose one repetition of c to get c-bb-c. c-bb-ab would also be ok. We could also choose more repetitions of c or a c followed by ab for the first part. So cc-bb-c and cab-bb-c would also be acceptable strings.

  • $\begingroup$ Thanks :). Does this mean I can make any combination of strings within (c U ab U b)*, right? Since the star represents strings that are >= 0? $\endgroup$
    – chompy
    Commented Jan 5, 2017 at 14:32
  • $\begingroup$ Yes. You can choose zero or more times one of c, ab, or b. $\endgroup$
    – adrianN
    Commented Jan 5, 2017 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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