classification of a language -- not ({ww})

I remember once a professor told me a wonderful method to derive
the following language.
{ x | x in (\sigma *) and x <> ww for any (w in \sigma *) }


Namely, it contains words that do not consist of 2 identical front and
hind parts. Now I forget how the grammer looked like and will
appreciate any information about it.


Beside, I also consider the question "Is this language Context Free?"


Surely {ww|w in (\sigma)*} is not context-free (i devised a context
sensitive grammar for it so i guess it is context sensitive). But the
context-free language is not closed for 'complementation' so we cannot
claim not({ww}) is not context-free. And I failed to disprove it by
pumping lemma, too.


BTW, is context sensitive language closed under 'complementation'?


Thanks in advance,


Linlist


--
-------------------------
Linlist Leo
linlist@fudan.edu

Return to the comp.compilers page.
Search the comp.compilers archives again.