Community  »  Perl: Allgemeines Forum

Ableitung eines regulären Ausdrucks	Seitenanfang
Hallo! Ich habe ein kleines (großes?) Problem. Hier mal die Aufgabe: ++++++++++ Entwicklung einer Methode zur Ableitung eines regulären Ausdruckes aus einer gegebenen Menge von Sätzen einer regulären Sprache, die durch diesen Ausdruck spezifiziert wird. Beispiel: Gegeben sind die Worte: a, baa, babaa, ab, abb, die zu der Sprache gehören und die Worte aa, bbaa, baba, die nicht zu der Sprache gehören Worte mit gleichem Präfix, die zu der Sprache gehören, werden zusammengefaßt: · a + ab + abb = a(e + b + bb) =verallgemeinert=> ab*. Überprüfung der Verallgemeinerung mit den Worten, die nicht zu der Sprache gehören - von diesen wird keines durch den Ausdruck abgedeckt: aa, bbaa, baba sind nicht Element von ab* · baa, babaa = (ba + baba)a = verallgemeinert=> (ba)+a. Überprüfung der Verallgemeinerung mit den Worten, die nicht zu der Sprache gehören - von diesen wird keines durch den Ausdruck abgedeckt: aa, bbaa, baba sind nicht Element von (ba)+a Damit ist der gesuchte Ausdruck: ab* + (ba)+a Wenn ein Wort, das nicht zu der Sprache gehört, durch einen Teilausdruck abgedeckt wird, dann ist dieser zu allgemein und er muß spezialisiert werden. Das Kann durch anhängen oder Voranstellen von Symbolen oder durch Benutzung einer Teilmenge geschehen. Z.B ist ab + abab spezieller als (ab)*. ++++++++++ Mit anderen Worten: Gegeben sind Strings, diese sollen nach Gemeinsamkeiten (Zyklen) durchsucht werden. Daraus soll dann der reguläre Ausdruck konstruiert werden. Anschließend erfolgt die Prüfung auf Korrektheit des regulären Ausdrucks anhand der Worte, die nicht zu der Sprache gehören. Ist der reguläre Ausdruck korrekt, endet der Algorithmus. Wenn nicht, startet die Prozedur von neuem (allerdings werden die Zyklen jetzt verkleinert). Kann man solch ein Problem mit Perl lösen? Ich muss gestehen, dass ich nicht so der ganz große Programmierer bin... Oder sollte man lieber eine andere Sprache nehmen, z.B. PHP oder Java (die ja auch reguläre Ausdrücke unterstützen)? Ich wäre sehr dankbar für jede Art von Tipps oder Hinweisen. MfG Moppel Datum: 11.05.2005-20:17
re: Ableitung eines regulären Ausdrucks	Seitenanfang
Ein guter Anfang könnte Regexp::Assemble sein: #! /usr/bin/env perl use strict; use warnings; use lib qw(/homes/myHome/); use Regexp::Assemble; my $ra = Regexp::Assemble->new(); $ra->add('^'.$_.'$') for(qw!a baa babaa ab abb!); print $ra->re,"\n"; Ausgabe: (?-xism:^(?:(?:ba)?baa|a(?:b?b)?)$) Das ist zwar noch nicht die endgültige Lösung, aber ein Anfang... Datum: 12.05.2005-09:01