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

| cite | improve this 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 '19 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 '19 at 12:12
  • $\begingroup$ Correct would be $(x + y) x (x + y)^*$ $\endgroup$ – 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!

| cite | improve this answer | | | | |

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