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

"Rodrigo Augusto B. Ferreira" <raugfer@uol.com.br>
28 Oct 1999 02:04:17 -0400

          From comp.compilers

Related articles
classification of a language -- not ({ww}) linlist@fudan.edu (Linlist Leo) (1999-10-27)
Re: classification of a language -- not ({ww}) raugfer@uol.com.br (Rodrigo Augusto B. Ferreira) (1999-10-28)
Re: classification of a language -- not ({ww}) torbenm@diku.dk (1999-10-29)
| List of all articles for this month |

From: "Rodrigo Augusto B. Ferreira" <raugfer@uol.com.br>
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

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





Post a followup to this message

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