# Basic regular expressions problem

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.

-

(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.

-
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

-