grep regexps
Lutz Donnerhacke
lutz at iks-jena.de
Mon Nov 19 10:02:54 CET 2001
* 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