Subject: Re: pumping-lemma
Date: Fri, 5 Jan 2001 08:52:28 +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:   660
Status: RO


> Ja, aber mit dem Pumping-Lemma kann ich doch "nur" nachweisen, das die
> Sprache kontextfrei ist - und das weiß ich ja schon.

neinneinnein, sowas kann man NIE mit pumping-lemma beweisen,
siehe das neue aufgabenblatt IVb 
http://www.informatik.uni-leipzig.de/~joe/edu/ws00/auspra/aufgaben/aufgabe4b.ps

mit der kontraposition des pumping-lemmas
(wenn KEIN n exist, so daß ... ,   dann ist L NICHT regulär)
kann man für einige (nicht alle, die man gern hätte) sprachen zeigen,
daß sie NICHT regulär sind.

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