Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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'm in an intro to CS theory class learning about regular expressions. I was wondering if people could give me hints as to whether I'm on the right track for these problems. I hope this particular stackexchange is able to help for such topics:

Give a regular expression that generates the following languages over $\{x, y\}$:

a. does not contain substring "$xxy$"

b. contains an even number of $x$'s or exactly 2 $y$'s

c. does not end in "$yx$"

My current solutions/ideas:

a. $y^{*}(xy^{+})^{*} \cup ({y^{*}}x^{*})$

b. $(\Sigma^{*}x\Sigma^{*}x\Sigma^{*})\cup(x^{*}yx^{*}yx^{*})$

c. $\Sigma^{*}(xx\cup y^{+})$

I'm wondering whether im on the right track for these problems and whether some of these solutions can be simplified further.

share|cite|improve this question
up vote 3 down vote accepted

(a) The requirement boils down to saying that once you get $xx$, you can never get a $y$. Your regular expression generates only valid strings, but it doesn’t generate all valid strings. For instance, it doesn’t generate $xyxx$. You want something like $y^*(xy^+)^*x^*$.

(b) The second part of your regular expression is fine: it generates precisely those words that contain exactly two $y$’s. The first part, however, doesn’t do what you want at all: it generates all words with at least two $x$’s. You need a regular expression that generates $x$’s in pairs; do you see why $y^*(xy^*xy^*)^*$ does the job?

(c) This almost works, but not quite: the empty string and the two one-character strings should also be generated.

share|cite|improve this answer
Thanks, this makes a lot of sense. – Matt Feb 22 '13 at 22:18
@Matt: You’re welcome. – Brian M. Scott Feb 22 '13 at 22:19

a) You don't have $yxyxx$

b) You seem to match also $xxx$

c) You don't have the empty word

share|cite|improve this answer

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.