So i am trying to proove that L = { u#w | u != w } (from {a,b}* ) is not a contex-free language.
With the pumping lemma i tried a^p # a^r , but how can i pump so they would become equal.
Or can I get it from {w#w| w in {a,b}* } (since we know it's not a contex-free language) using only contex-free operations (union, concatenation ...) Any tips ?
It is context free.
We have two cases: $|u| \neq |w|$ or $u = p m q$ and $v = r n s$ for some strings $p, q, r, s$ s.t. $|p| = |r|$ and $m, n \in \{a, b\}$, $m \neq n$.
Language $\{u\#w|\ |u|\neq |w|\}$ is generated by grammar ($S$ is starting non terminal) $$C \to a|b$$ $$S \to L | R$$ $$L \to CL|CE$$ $$R \to RC|EC$$ $$E \to \# | CEC$$ ($C$ generates single symbol, $L$ generates words with more symbols before $\#$ than after, $R$ with more symbols after $\#$ and $E$ with equal number of symbols)
Language $\{u\#w | u = pmy, v=qrs, m \neq n, |p|=|q|\}$ is generated by $$C \to a|b$$ $$D \to CD | \varepsilon$$ $$S \to AbD | BaD$$ $$A \to CAC|aD\#$$ $$B \to CBC|bD\#$$ ($D$ generates all words, $A$ generates words of form $p b q \# r$ where $|p| = |r|$ and $B$ generates words of form $p a q \# r$)
It's essentially CFG version of this answer on cs.se by @babou.