# Regular Expression: Writing an expression with at least two characters in length? [closed]

A past exam question: (1) Consider the language, $$L$$, of strings over the alphabet $$\{x, y\}$$ of length at least 2 with the second symbol being $$x$$. For example, $$yx$$, $$xxyy$$, and $$yxy$$ are members of $$L$$ while $$xy$$, $$yyy$$, and $$yyxx$$ are not in $$L$$.

(a) Write a regular expression to describe the language $$L$$.

I thought perhaps $$\Sigma x\Sigma^*$$ would be the correct answer, but then $$\Sigma$$ could be either an empty string or $$x$$ or $$y$$, and the empty string would make it no longer valid because $$x$$ wouldn't be the second symbol. Is there some kind of expression that could mean $$(x + y)x\Sigma^*$$?

• If E "="$\Sigma = \{x, y\}$ is your alphabet it usually works as a shortcut for exactly $(x+y)$ not for $(x+y+\varepsilon)$. – ttnick Jul 30 '19 at 15:04
• $(x+y)x\Sigma^*$ is a regular expression that means $(x+y)x\Sigma^*$ so I don't understand what your question is. – David Richerby Aug 7 '19 at 12:12
• Correct would be $(x + y) x (x + y)^*$ – vonbrand Aug 7 '19 at 17:10

$$\Sigma$$ does not include the empty string; it only contains the characters of the language, and the empty string is not a character. As user ttnick said in a comment, in general, if $$\Sigma=\{x_1,x_2,\dots,x_n\}$$, then "$$\Sigma$$" in a regex represents $$x_1 + x_2 + \dots +x_n$$ (equivalently $$x_1 \cup x_2 \cup \dots \cup x_n$$, depending on what notation you're using). The empty string comes from taking the Kleene star ($$\Sigma^*$$) of the alphabet $$\Sigma$$.
For a tiny bit of theory background, this is because we want the Kleene star to produce a monoid, which is a mathematical object that 1) has an associative composition operation—in this case, string concatenation—and 2) has an element $$\varepsilon$$ such that for any other element (string) $$s$$, we have $$\varepsilon s=s\varepsilon=s$$. Intuitively, you can think of the Kleene star $$\Sigma^*$$ as "the set of strings $$s$$ such that all characters in $$s$$ are in $$\Sigma$$", and this is clearly (though vacuously) true of the empty string!