patternMinor
What does the symbol # mean when it comes to languages
Viewed 0 times
thewhatsymbollanguagesmeandoeswhencomes
Problem
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?
$$\{ w\#x \mid w^R \text{ is a substring of $x$, with $x$ and $w \in \Sigma^*$} \}$$
What does $w\#x$ denote?
Solution
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}\}$$
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}\}$$
Context
StackExchange Computer Science Q#18630, answer score: 5
Revisions (0)
No revisions yet.