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^*$?


closed as unclear what you're asking by Evil, xskxzr, dkaeae, David Richerby, vonbrand Aug 7 at 17:10

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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


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