1
$\begingroup$

It is pretty hard for me to understand, how binary representation of number may be context free. This language $L=\{bin(n)bin(n+1)^R : n \geq 0\}$ is context free.

Here, at 1.b, is a PDA which describes this language, so it is context free. I've tried to construct a context free grammar for this one, but I have no idea when to even start. How can I express a CFG binary representation of a number? I would be very glad for any suggestions.

$\endgroup$
2
$\begingroup$

Here is one solution: $$ \begin{align*} &S \to 01 \mid 1A1 \mid 1B1 \\ &A \to 1A0 \mid 0 \\ &B \to 1B1 \mid 0B0 \mid 0C1 \\ &C \to 1C0 \mid \epsilon \end{align*} $$

Explanation:

  • $A$ generates $1^n 0^{n+1}$, and so $1A1$ generates $1^{n+1} 0^{n+1}1$, which handles numbers whose binary expansion is $1^{n+1}$.
  • $C$ generates $1^n 0^n$, and so $0C1$ generates $01^n 0^n1$.
  • $B$ generates $w01^n0^n1w^R$, and so $1B1$ generates $1w01^n0^n1w^R1$, which handles numbers whose binary expansion is $1w01^n$.
  • Finally, $01$ handles $0$.
$\endgroup$
  • $\begingroup$ Thanks for your answer. Do you know meybe grammar for $L = \{bin(n)bin(n+1) : n \geq 0\}$ ? It's same, but without reversing $bin(n+1)$ $\endgroup$ – maqo May 27 '17 at 12:26
  • $\begingroup$ That language isn't context-free. $\endgroup$ – Yuval Filmus May 27 '17 at 13:02
  • $\begingroup$ Do you meybe know word for pumping lemma, which I could use to prove that it is not context free ? $\endgroup$ – maqo May 27 '17 at 13:16
  • $\begingroup$ It's a very standard exercise. You can also try reducing to the language $a^nb^mc^nd^m$. $\endgroup$ – Yuval Filmus May 27 '17 at 13:35

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.