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$

1 Answer 1

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$
4
  • $\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, 2017 at 12:26
  • $\begingroup$ That language isn't context-free. $\endgroup$ May 27, 2017 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, 2017 at 13:16
  • $\begingroup$ It's a very standard exercise. You can also try reducing to the language $a^nb^mc^nd^m$. $\endgroup$ May 27, 2017 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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