theory of computation

Question

Determine whether or not the following language is context-free.

MY ANSWER : The given language is equivalent to L₁ = { ww^R : where w $\in$ {a,b}^* } . And so the given language is Non-deterministic CFL.

Please verify ...

Comments

how are both equivalent??

Answer 1

Actually for such languages what we do is : 

By appropriate substitution ( in this case n = 0 ) , if we are able to cover higher strings (like n = 1 , 2 etc here ) , then we can do such substitution.

For example to verify here , we can see that here we have any no of a's in the beginning and in the end also ..So the starting 'n' a's can be made part of 'w' part of string and trailing 'n' a's can be made part of 'w^R'  part of string..

Hence the given language reduces to L = { w w^R  |  w belongs to {a , b}* } which is an NCFL..Hence the given language is NCFL.