From joe Wed Dec 20 09:23:41 2000
Subject: Re: Anfrage zu Aufgabe 44b
Date: Wed, 20 Dec 2000 09:23:41 +0100 (MET)
X-Mailer: ELM [version 2.4ME+ PL61 (25)]
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
Content-Length:  2019
Status: RO

vielen dank für die frage zu Aufgabe44b. 

es war tatsächlich ein fehler in meinem testprogramm:
ich hatte {a, b} als alphabet, aber in der aufgabenstellung steht {0, 1}
damit konnte es gar nichts werden. das habe ich jetzt korrigiert.


Ihre grammatik stimmt trotzdem nicht, 
soweit ich sehe, erzeugen Sie *nur* wörter ungerader länge.

> ww bedeutet doch sinngemäß: alle Wörter mit gerader Länge. 

... bei denen die erste mit der zweiten hälfte übereinstimmt.


die aufgabenstellung leidet etwas darunter,
daß die quantoren fehlen bzw. falsch stehen. gemeint ist:

Lb = {  x  |  x in {0,1}+  und  für alle  w  in  {0,1}+  gilt  x /= ww  }

das sind also alle wörter, die *nicht* die form  ww  haben.


> Sind also nicht alle ungeraden Wörter in der geforderten Sprache enthalten?

doch. alle wörter ungerader länge sind in Lb, 
aber außerdem viele wörter mit gerader länge.

die wörter bis zur länge 6 sind (in lexikografischer reihenfolge)

["0","000","00000","000001","00001","000010","000011","0001","00010",
"000100","000101","00011","000110","000111","001","0010","00100",
"001000","00101","001010","001011","0011","00110","001100","001101",
"00111","001110","001111","01","010","0100","01000","010000","010001",
"01001","010011","01010","010100","010101","01011","010110","010111",
"011","0110","01100","011000","011001","01101","011010","0111","01110",
"011100","011101","01111","011110","011111","1","10","100","1000",
"10000","100000","100001","10001","100010","100011","1001","10010",
"100101","10011","100110","100111","101","10100","101000","101001",
"10101","101010","101011","1011","10110","101100","10111","101110",
"101111","110","1100","11000","110000","110001","11001","110010",
"110011","1101","11010","110100","110101","11011","110111","111",
"1110","11100","111000","111001","11101","111010","111011","11110",
"111100","111101","11111","111110"]

-- 
-- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ --
-- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --