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

Linlist Leo <>
27 Oct 1999 14:28:44 -0400

          From comp.compilers

Related articles
classification of a language -- not ({ww}) (Linlist Leo) (1999-10-27)
Re: classification of a language -- not ({ww}) (Rodrigo Augusto B. Ferreira) (1999-10-28)
Re: classification of a language -- not ({ww}) (1999-10-29)
| List of all articles for this month |

From: Linlist Leo <>
Newsgroups: comp.compilers,comp.theory
Date: 27 Oct 1999 14:28:44 -0400
Organization: Compilers Central
Distribution: inet
Keywords: parse, theory

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 Leo

Post a followup to this message

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