CFG for $w\#x$ where $|w| = |x|$ and $w \neq x^R$

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

1 Answer

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$$.

• So would you say something like $\\ S -> A0B\#B1A | A1B\#B0A \\ A -> 0|1|epsilon \\ B ->0|1|epsilon$ – George Walker Apr 10 '20 at 16:45
• 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$. – Yuval Filmus Apr 10 '20 at 16:51
• From now on, I will not check any more "answers". The hints in my answer should be enough for you to solve the exercise. – Yuval Filmus Apr 10 '20 at 16:51