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

"Rodrigo Augusto B. Ferreira" <>
28 Oct 1999 02:04:17 -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: "Rodrigo Augusto B. Ferreira" <>
Newsgroups: comp.compilers,comp.theory
Date: 28 Oct 1999 02:04:17 -0400
Organization: Institute of Computing, University of Campinas, SP, Brazil
Distribution: inet
References: 99-10-132
Keywords: parse, theory


L = { x | x in (\sigma *) and x <> ww for any (w in \sigma *) },
L IS context free although its complement is not.

A context free grammar is given below. The basic idea is
to generate all odd length strings and those even length
string in each at least one terminal in position n differs
from the one in position 2*n. See picture:

or <---m--->b<---n---><---m--->a<---n--->

the trick is to "invert" the substrings in the middle of
the strings, then we can easilly visualize how to build
a context free grammar.

or <---m--->b<---m---><---n--->a<---n--->

Grammar for \sigma = {a,b}

S -> AB|BA|C
A -> aAa|aAb|bAa|bAb|a
B -> aBa|aBb|bBa|bBb|b
C -> aCa|aCb|bCa|bCb|a|b

Hope it helps,
but do not use it for academical benefit ;)

Rodrigo Augusto.

Linlist Leo wrote:
> 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 *) }
Rodrigo Augusto B. Ferreira
Computer Science Graduate, UFMG/BRAZIL

Post a followup to this message

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