Given grammar G, I have to prove it defines the language of all words which are not palindromes.
In other words, $w\in L(G) \Leftrightarrow w\in L $ where $L =$ {w$\in$ $\sum^*$ | w is not palindrom}
G:
$R → URU | S$
$S → aT b | bT a$
$T → UT U|U |\epsilon$
$U → a | b$
Tried to do so using induction for each side:
$w\in L(G) \Leftarrow w\in L $ on the size of w ,|w|
$w\in L(G) \Rightarrow w\in L $ on the number of steps in the grammar.
Had no luck so far, any help will do.
Thanks in advance.
First of all, let us note that $$ L(T) = \{ xyz : |x| = |z|, |y| \leq 1\} = \Sigma^*, $$ since every natural number can be written as $2n$ or as $2n+1$.
Similarly, $$ L(R) = \{ x \sigma y \tau z : |x| = |z|, \sigma \neq \tau \}. $$ Since $(x\sigma y \tau z)^R = z^R \tau y^R \sigma x^R$ and $|x| = |z^R|$, each such word isn't a palindrome.
Conversely, suppose that $w$ isn't a palindrome. Then $w^R \neq w$. Suppose that $w,w^R$ differ on the $i$th letter, that is, $w_i \neq w^R_i = w_{n+1-i}$, where $n = |w|$. The two words also differ on the $(n+1-i)$th letter, so $i \neq n+1-i$, and we can assume that $i < n+1-i$, implying $2i \leq n$. We can therefore write $w = x \sigma y \tau z$, where $|x| = |z| = i-1$ and $|y| = n-2i \geq 0$. Then $\sigma = w_i \neq w_{n+1-i} = \tau$, showing that $w \in L(R)$.