Мне бы очень хотелось, чтобы вы помогли решить, является ли язык всех слов в алфавите {0,1}
тем, что не может читаться с обеих сторон одинаково, { w | w <> w R}
, является контекстно-свободным языком (то есть может быть преобразован в конкретные правил грамматики).
Я пытался доказать, что это не контекстно-свободный язык, используя лемму о накачке, но не нашел строки, которая привела бы меня к противоречию.
Есть предложения?