"Regulärer Abschluß" einer kontextfreien Sprache?

thecow · Gast

Hi, ich suche ne Möglichkeit zu einer gegebenen Kontextfreien Sprache CFL eine reguläre Sprache RL so zu bestimmen dass

a) jedes Wort w welches in CFL ist auch in RL ist
b) möglichst wenige Wörter v welche nicht in CFL sind in RL sind
c) RL möglichst effizient aus CFL kontruiert werden kann

z.B. wenn CFL = a^n b^n dann wär RL = a*b*, alle Wörter die c's enthalten oder Konstrukte wie aba oder bab würden damit schonmal rausfallen.

Wenn jemand da Ideen hat bzw. nen Algorithmus kennt wäre ich ihr/ihm sehr verbunden.

Danke

Daniel

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Interessante Fragestellung, aber:

1. Wie ist die Sprache CFL gegeben? Als Kontextfreie Grammatik? Wie soll die Antwort aussehen?

2. Wie definierst du 'moeglichst wenig' bei unendlich grossen Mengen?

3. Was genau ist 'moeglichst effizient'?

Aber ich halte das Problem fuer schwierig :)