From joe Tue Nov 7 10:51:26 2000 Subject: Re: AW: Frage Date: Tue, 7 Nov 2000 10:51:26 +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: 1380 Status: RO die definition der hülle, also (ich schreibe lieber X*) ist X* = (leeres wort) + X mal X* jetzt setzen wir X = (leere menge) ein (leere menge)* = (leeres wort) + (leere menge) mal (leere menge)* bei der multiplikation (im zweiten summanden) spielt der rechte faktor gar keine rolle, weil der linke die leere menge ist. wie gestern schon gesehen gilt für jedes Y (leere menge) mal Y = leere menge deswegen (leere menge)* = (leeres wort) + (leere menge) = (leeres wort) man kann (aber nur ganz vorsichtig) an das rechnen mit zahlen denken, 1 = die menge, die nur das leere wort enthält, 0 = die leere menge. + = vereinigung * = konkatenation wenn Ihnen jemand eine gleichung zeigt S = 1 + X mal S dann denken Sie S - X * S = 1 S * (1 - X) = 1 S = 1 / (1 - X) und wenn jetzt X = 0 (leere menge), folgt S = 1 / (1 - 0) = 1 / 1 = 1 ( = leeres wort) für beliebige X haben wir natürlich bei formalen sprachen (d. h. mengen) kein "minus", aber es gibt ja potenzreihen: S = 1 / (1 - X) = 1 + X + X * X + X * X * X + ... das gilt bei zahlen und auch bei sprachen. das liegt daran, daß beide bereiche (polynome, formale Sprachen) Ringe sind. -- -- Johannes Waldmann ---- http://www.informatik.uni-leipzig.de/~joe/ -- -- joe@informatik.uni-leipzig.de -- phone/fax (+49) 341 9732 204/252 --