Re: RE-Problem

Datumsansicht Baumansicht Betreffansicht Attachement-Sicht

From: Mathias Waack (mathias_at_mufasa.informatik.uni-mannheim.de)
Date: 24. May 2000


Hi,

On 24-May-2000 Christian Weisgerber wrote:
> Juergen Unger <dwalin_at_addict.de> wrote:
>
>> das geht IMHO nicht mit nur einer regex,
>
> 1. Kann das jemand bestdtigen?

Ja.

> 2. Warum?

Weil regulaere Ausdruecke nicht zaehlen koennen. Regulaere Ausdruecke
sind ein Aequivalent zu endlichen (Zustands-)Automaten. An letzteren
kann man das besser zeigen:
        sed "s/\(.\)^H\1/<fett>\1<\/fett>/g"
(ich bin keine Experte bei regulaeren Ausdruecken)
Die ist wohl ein Automat, der fuer jeden Buchstaben des Alphabetes
einen Zustand hat um zu checken, ob ein ^H und derselbe Buchstabe
folgt:

        ----- ------ ------
------> | a | ------> | ^H | ------> || a ||
   | ----- | ------ ------
   |<------------/
   |
   \--> b ------> ^H ------> | b |
   ...

Kommt der Automat in einen Endzustand ( || a ||), gilt der Ausdruck
als erkannt. Jetzt muesste der Automat weiterlaufen, um zu sehen,
ob er gleich nochmal "sein" Muster erkennt. Man muesste jetzt also
in unserem obigen Automaten alle Endzustaende quasi nochmal
durch den ganzen Automaten ersetzen. Dann haette man einen
Automaten, der x^Hx^Hx erkennt und daraus <fett>xx</fett>
macht. Folgt dem aber noch ein x^Hx, so haben wir wieder
<fett>xx</fett><fett>x</fett>. Jetzt sollte das Problem schon
klar werden.

Wir haben hier sowas wie den Klassiker (an)(bn), wobei
(an) bedeutet, dass a n-mal hintereinander stehen soll.
Der Automat (oder die RE) soll also Terme ala ab aabb aaabbb usw.
erkennen. Durch den Beweis sollte IMHO jeder Informatiker mal durch.

> Haben wir hier nicht ein paar studier(end|t)e Informatiker?

Je nu, ich hoffe ich muss mich dafuer nicht entschuldigen;)
Immerhin wuerde ich jeder engagierte Prof. fuer den Pseudobeweis
da oben lynchen. Falls es gewuenscht wird, kann ich auch gerne
einen formalen Beweis nachschieben, das kostet denn aber was.
Unter 2 Bier fang' ich nicht an zu arbeiten;)

> Sei angemerkt, dass man
> - einem sed-Aufruf mehrere Ausdr|cke unterschieben kann. Au_er dem
> unleserlichen Aneinanderreihen mit ';' kann man auch mehrere
> Argumente "-e <Ausdruck>" |bergeben.

Was hier nicht hilft, es sei denn Du nimmst Dir die Zeit, einen
unendlichen Automaten dafuer zu konstruieren.

> - bei sed das Begrenzungszeichen f|r REs frei wdhlen kann, was
> hilft, das "leaning toothpick syndrome" (/\/\/...) zu vermeiden.

Was IMHO (korrigiert mich bitte) ein allgemeines Feature von RE
unter Unix ist?

Mathias, der sich jetzt hoffentlich nicht blamiert hat, das liegt
        alles schon etwas zurueck


Datumsansicht Baumansicht Betreffansicht Attachement-Sicht

Dieses Archiv wurde generiert von hypermail 2.1.2 : 11. Mar 2002 CET