Является ли WW, где W принадлежит {a,b}*, контекстно-свободным языком?

Нет

Предположим, ради противоречия, что это так, тогда есть КПК, которые его принимают.

Согласно лемме о накачке (для CFG), существует длина p такая, что для каждого слова (мы вскоре выберем одно) s существует некоторая подстрока u,v,w,x,y такая, что s=uvwxy и:

1. |vwx|<=p
2. |vx|>=1
3. uv^n wx^n y на языке для любого положительного n

Рассмотрим слово a^p b^p a^p b^p и такие u,v,w,x,y

Либо vwx содержит середину слова, либо полностью содержится в первой половине, либо полностью содержится во второй половине.

Если в первой половине, то в слове uv^2 wx^2 y. Мы добавили общую длину не более чем на p, таким образом, мы "переместили" среднюю точку не более чем на p/2, так что прямо сейчас средняя точка продолжается с b, но слово начинается с a, так что это не так. формы ww

Тот же аргумент касается того, что это происходит во второй половине.

Теперь давайте предположим, что он содержит середину, и рассмотрим uwy (используя n=0). Начиная с |vwx|<=p, мы удалили а и б в середине, но не из а и б по краям. Мы также удалили положительное количество букв, поэтому uwy имеет форму a^p b^k a^m b^p, где либо k<p, либо m<p. В любом случае, это не форма ww