grep regexps

[Lutz Donnerhacke]

* Matthias Czapla wrote:
>On Sun, Nov 18, 2001 at 09:27:28PM +0000, Lutz Donnerhacke wrote:
>> Oder eben mit der inversen RegEx, die nach Theorie existieren muß
>> (RegEx ist Typ2 und damit unter Schnitt, Vereinigung und Komplement
>> abgeschlossen).
>
>Ich weiss nicht, was du meinst. Hast du eventuell Links zu dem Thema? Ich
>konnte bei google nichts finden.

Jedes Lehrbuch "Grundlagen der theoretischen Informatik" enthält den Beweis.

Eine Typ2 Sprache kennt folgende Produktionen (Großbuchstaben bezeichnen
Nichtterminal, Kleinbuchstaben Terminale) für jedes Nichtterminal:
  Entweder A -> BC oder A -> a.

RegEx ist bekannt:
  .     - Beliebig
  ^     - Beginn
  $     - Ende
  [xyz] - Eins aus der Menge
  [^xy] - Alles nur nicht eins aus der Menge
  X?    - optional X
  X*    - X beliebig oft wiederholt
  XY    - X und direkt danach Y
  X|Y   - X oder Y

Komplementbildung (!):
  ![xyz] -> [^xyz]
  !(XY)  -> X!Y | !XY | !X!Y

Man muß nun alles anderen Konstrukte nur in die Form XY bringen und dann das
Komplement bilden ...

-- 
tlug Mailingliste
Archiv: http://www.tlug.de/archiv/
http://schwarz.thueday.de/mailman/listinfo/tlug_allgemein