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.