Subject: Re: Aufgabe 42b
Date: Thu, 4 Jan 2001 14:30:33 +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:  1311
Status: RO


> Die Grammatik zu Aufgabe 42a: läßt sich eine gefundene Grammatik mittels
> irgendeines Verfahrens noch minimieren?

das ist nicht so leicht. schon für kontextfreie grammatiken G1, G2
läßt sich NICHT immer entscheiden, ob L(G1) = L(G2).
um so schwerer die frage, ob es zu G1 ein kleiners G2 mit L(G1) = L(G2) gibt.

endliche automaten (d. h. reguläre sprachen) 
macht man erst deterministisch und dann minimal.
diese heißen zwar minimal, sind aber u.U. sehr groß,
verglichen mit einem nichtdeterministischen (siehe aufgabe V.4
http://www.informatik.uni-leipzig.de/~joe/edu/ws00/auspra/aufgaben/aufgabe5.ps)

schon auf die frage nach dem kleinsten NICHTdeterministischen
endlichen automaten für eine gegebene reguläre sprache
kennt man keine vernünftige (praktikable) antwort.
übungsaufgabe: finde eine reguläre sprache L, so daß
L einen kleinen nichtdet. automaten besitzt,
aber das komplement von L keinen. siehe teil 1 des vortrags:
http://www.informatik.uni-leipzig.de/~joe/talk/ata.ps


dann ist also bei kontextsensitiven grammatiken mit sicherheit alles zu spät.

natürlich fallen einem von fall zu fall dann doch noch
irgendwelche heuristiken ein. 

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