# What does the symbol # mean when it comes to languages

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?

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$.

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