Given the following:

$$\{ w\#x \mid w^R \text{ is a substring of $x$, with $x$ and $w \in \Sigma^*$} \}$$

What does $w\#x$ denote?


2 Answers 2


This seems to just be a case of a lack of care in the definition. The symbol $\#$ isn't anything special, but is commonly used as a separator simply for the reason that it's not normally used for much else.

So in the language in question, all the strings in the language have two parts, $w$ and $x$, which are separated by the character $\#$, so you can easily tell which part of the string you're processing (just by keeping track of whether you've gone past the $\#$ or not).

Implicitly the strings $w$ and $x$ do not include the symbol $\#$, but the way it's written (at least in the question) this is not clear.

So, assuming that my interpretation is correct, a more explicit definition might be:

Let $L$ be a language over $\Sigma\cup\{\#\}$, where $\# \notin \Sigma$ such that $$L = \{w\#x \mid w^{\mathcal{R}}\text{ is a substring of } x, \text{ and } w,x\in\Sigma^{\ast}\}$$


Usually $\#$ is just a symbol of the alphabet, i.e. $\# \in \Sigma$. And $w\#x$ is just concatenation of the word $w$, the symbol $\#$, and the word $x$.

  • 1
    $\begingroup$ But the point here is that it's a special symbol, not included in either $w$ or $x$. $\endgroup$ Dec 5, 2013 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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