How do I construct a context-free grammar for the following language?

$$L = \{w\#x \mid w, x \in \{0, 1\}^*, |w| = |x|, w \neq x^R \} $$


A word belongs to your language if it has one of the following forms: $$ \Sigma^i 0 \Sigma^j \# \Sigma^j 1 \Sigma^i \\ \Sigma^i 1 \Sigma^j \# \Sigma^j 0 \Sigma^i $$ Given this, you should be able to construct a context-free grammar for $L$.

  • $\begingroup$ So would you say something like $ \\ S -> A0B\#B1A | A1B\#B0A \\ A -> 0|1|epsilon \\ B ->0|1|epsilon$ $\endgroup$ – George Walker Apr 10 '20 at 16:45
  • $\begingroup$ Your grammar generates palindromes: $S \to A0B\#B1A \to 10B\#B1A \to 10\#B1A \to 10\#01A \to 10\#01$. It also doesn't guarantee that $|w| = |x|$: $S \to A0B\#B1A \to 0B\#B1A \to 0\#B1A \to 0\#1A \to 0\#10$. $\endgroup$ – Yuval Filmus Apr 10 '20 at 16:51
  • $\begingroup$ From now on, I will not check any more "answers". The hints in my answer should be enough for you to solve the exercise. $\endgroup$ – Yuval Filmus Apr 10 '20 at 16:51

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.