Is { ш | w <> w^R } над алфавитом {0,1} контекстно-свободный язык?

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

Я пытался доказать, что это не контекстно-свободный язык, используя лемму о накачке, но не нашел строки, которая привела бы меня к противоречию.

Есть предложения?

12
задан Eitan T 5 August 2012 в 05:43
поделиться