# Is the following language regular; context-free but not regular; or not context-free?

Let $$\Sigma=\{0, 1, \#\}$$.

Is the following language regular; context-free but not regular; or not context-free?

Justify your answer $$L=\{x\#y :\ x, y \in\{0, 1\}^∗\text{ and }\operatorname{bin}(x) + 1 = \operatorname{bin}(\operatorname{rev}(y))\}$$

• What are $\operatorname{bin}(x)$ and $\operatorname{rev}(y)$? I could guess the first is the number which binary representation is $x$ and the second is the reversed word. Is that the case? If so, if you take a word in $L$, for which $x$ is longer than the pumping length, then when you pump the word it will eventually fall out of $L$. Observe that the operation of adding $1$ can at most increate the length by $1$, but the pumping can make the part before the $\#$ arbitrarily longer than the part after the $\#$.
– plop
Mar 18 at 12:28
• This site has a convenient search option: Context free grammar for bin($n$)bin$(n+1)^R$ Mar 22 at 23:57

Denote your language by $$L$$. Notice that $$L \cap 1^*\#0^*1 = \{ 1^n \# 0^n 1 : n \geq 0 \},$$ which should suffice for showing that $$L$$ isn't regular.
On the other hand, $$L = \{ 0^a1^n \# 0^n 10^b : n,a,b \geq 0 \} \cup \{ 0^ax01^n \# 0^n1x^R0^b : n,a,b \geq 0, x \in \{0,1\}^* \},$$ which should suffice for showing that $$L$$ is context-free.