Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an alphabet $A = \{b,B\}$ and I'm asked to write down the pattern of the regular expression $(\epsilon|bb|b)(B|bb)(b|\epsilon|b)$. What does the question actually want me to do? I'm not sure. Does it want me to give the possible patterns that can be formed with $b$ and $B$? But then surely the question would not have been phrased the way it is.

I'm just confused about what I need to do here and what is expected of the answer. If anyone could give an example it would be very helpful.

Note: This is not the original question, I changed and simplified it.

share|cite|improve this question
Maybe you simplified away the essence? – Raphael Jan 24 '13 at 12:52
@Raphael - I'm sure I didn't. The only problem that I'm having is to understand what is meant by giving the pattern. Knowing the alphabet and the regular expression. For instance is it to give the pattern where b and B are concatenated? and how many patterns you can create with that for example , bBb, bB etc ? – user1070241 Jan 24 '13 at 13:16
Maybe ['B', 'Bb', 'bB', 'bBb', 'bb', 'bbB', 'bbBb', 'bbb', 'bbbb', 'bbbbb']? – Pål GD Jan 24 '13 at 13:27
@PålGD That would be the language; I have not encountered 'pattern' as a synonym. There are pattern languages, though, but none of them can be generated by this regular expression – Raphael Jan 24 '13 at 14:14
If it is an exercise, ask the person who compiled the exercise. 'Pattern' is overloaded heavily, so we have little chance of guessing what is meant. – Raphael Jan 24 '13 at 14:14
up vote 1 down vote accepted

A pattern (in the context of languages and automata) is a way of defining a set of strings. A string matches a pattern if it belongs in the set defined by that pattern. So, your regular expression is actually a pattern. The question, I think, would be to find the pattern given a set of strings!

share|cite|improve this answer
Well, the problem is that what is given is a regular expression pattern. But it's somewhat convoluted, so it should apparently be simplified. – Jan Hudec Jan 25 '13 at 13:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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