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

Hi,


Given
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:


      <---m--->a<---n---><---m--->b<---n--->
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.


      <---m--->a<---m---><---n--->b<---n--->
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 ;)


Regards,
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
raugfer@uol.com.br

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