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))\}$$

  • 1
    $\begingroup$ 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 $\#$. $\endgroup$
    – plop
    Mar 18 at 12:28
  • $\begingroup$ This site has a convenient search option: Context free grammar for bin($n$)bin$(n+1)^R$ $\endgroup$ 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.

  • $\begingroup$ That’s part of your exercise. $\endgroup$ Mar 19 at 5:35
  • $\begingroup$ Thanks. I get that the first part shows L is not regular as there is not counting in regular languages and so there cannot be 1^n and 0^n together. May you elaborate on why the second equation is true? L={0^a 1^n#0^n 10^b ∶n,a,b ≥0}∪{0^a x01^n#0^n 1x^R 0^b:n,a,b≥0,x∈{0,1}^*} $\endgroup$
    – JYCT
    Mar 21 at 5:59
  • $\begingroup$ The second part does how to decompose words in the language in a way which allows generating them using a context-free grammar. $\endgroup$ Mar 21 at 6:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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