context free language

Question

Show that the language L={xy∣|x|=|y|,x≠y} is context free. Do not give links plz explain in simple manner

Comments

@Ashwin Kulkarni, How can we find that this grammar is CFL? I didn’t understand using the link provided!

---

Is the language also regular?

---

No its not regular as we want the length's of x and y equal and counting is not done by FA due to finite memory

Answer 1

we can take it as wwr .

where x=w

and y=wr so |x|=|y| and it is cfl.

Comments

It is also given  x=!y

x = 101 (w)

y =  101 (w^r)

for this case above explanation is not valid.

---

Awesome! Partially correct but most intuitive answer.

Answer 2

Can use non-determinism of PDA's to give a simple argument.

Non-deterministically compare 2 positions $\frac n2$ distance apart, if match not found, accept.

Proof is likewise. Only thing reamins in proof is to come up with a way to compare 2 characters $\frac n2$ distance apart.
That can be achieved by pushing some portion (let say length x) on stack, then emptying the stack and store the input symbol in finite automation when stack gets empty.
Once empty, push some portion (let say length y) on stack, then compare current input symbol with symbol in finite automation.
If symbol matches, then branch is discarded, If symbol doesn't match we pop the remaining contents of the stack,
if stack is empty at the end of input, string is accepted, otherwise branch is rejected.
If all branches are rejected, we reject the string.