In der Uni müssen wir die Chomsky-Hierarchie lernen. In welche Klasse/Typ sind reguläre Ausdrücke aka Regex/regular expressions einzuordnen? Kann man damit irgendwie eine Turingmaschine konstruieren?
|
41 ● 1 |
| 1 |
Ich glaube du solltest deine Frage etwas mehr ausformulieren, so verstehen das nur wenige.
|
2 Antworten
Reguläre Ausdrücke sind eine alternative zu regulären Grammatiken (auch bekannt als linkslineare/rechtslineare Grammatiken) zur Beschreibung von regulären Sprachen. Deswegen heißen sie ja "reguläre" Ausdrücke. Das heißt, reguläre Ausdrücke können exakt dieselben Sprachen erkennen, die von einer Typ-3-Grammatik beschrieben werden können und das sind ja genau die Typ-3-Sprachen. Das sind ebenfalls exakt dieselben Sprachen, die ein endlicher Zustandsautomat erkennen kann.
Aber Vorsicht: du schreibst in deiner Frage "reguläre Ausdrücke aka Regex". Das ist falsch! Regex und reguläre Ausdrücke sind nicht dasselbe! Sie sind nur entfernt verwandt: die Syntaxen von Regex basieren zwar lose auf regulären Ausdrücken, aber die Semantik ist zum einen signifikant anders, zum anderen deutlich mächtiger. So sind reguläre Ausdrücke nicht-deterministisch, Regex dagegen sind deterministisch.
Ein Beispiel für den Nicht-Determinismus ist, dass für den Kleene-Operator * nicht definiert ist, wie oft er matcht, bei Regexen ist das dagegen definiert: üblicherweise matcht er soviel wie möglich ("greedy") und es gibt eine Variante (den *? Operator), die sowenig wie möglich matcht ("lazy").
Wie schon erwähnt, sind Regexen üblicherweise auch mächtiger als reguläre Ausdrücke. Das heißt, Regexen können Sprachen erkennen, die nicht von einer Typ-3-Grammatik beschrieben und einem endlichen Zustandsautomaten erkannt werden können. Zum Beispiel gibt es meistens sogenannte "Backreferences" (Rückverweise), mit denen in einer Regel auf frühere erkannte Fragmente zurückgegriffen werden kann.
Übrigens: es gibt eine ganze Menge Bequemlichkeits-Erweiterungen in Regexen, die sie nicht mächtiger machen als reguläre Ausdrücke:
Welche Sprachklasse Regexen erkennen können, ist meistens nicht exakt definiert und ist schwer zu sagen, da oft die Semantik von Regexen nicht exakt formal definiert ist, sondern von der Implementierung abhängt. Außerdem gibt es nicht die Definition von Regexen, fast jede Regex-Implementierung hat ihre eigenen Erweiterungen, ihre eigene Syntax, ihre eigene Semantik. Zum Beispiel haben Perl-Regexen eine andere Syntax und Semantik als Ruby-Regexen. Und selbst innerhalb von Ruby gibt es massive Unterschiede zwischen Ruby 1.8 und Ruby 1.9.
Eines kann man mit ziemlicher Sicherheit sagen: praktisch jede Regex-Implementierung erkennt weitaus mehr als nur die regulären Sprachen, weswegen es eigentlich vollkommen unpassend und irreführend ist, sie als reguläre Ausdrücke oder regular expressions zu bezeichen. (Larry Wall, der Erfinder und Diktator von Perl, hat deswegen verfügt, dass in Zukunft nur noch von "Regexen" gesprochen werden darf, damit keine Verwirrung entsteht.) Ob Regexen jedoch alle Typ-2-Sprachen erkennen oder nur einige, oder ob sie gar mehr als die Typ-2-Sprachen erkennen, das hängt von der Implementierung ab, und ist praktisch nie vernünftig dokumentiert.
Ich habe zum Beispiel das unbestimmte Gefühl, dass die Regexen von Ruby 1.9 Turing-mächtig sind, das heißt sie können alle Typ-0-Sprachen erkennen. Ruby-1.9-Regexp haben benannte Funktionen, Funktionsaufrufe, Entscheidung, Schleifen und Rückverweise. Ich vermute (kann es aber nicht beweisen), dass sie damit Turing-mächtig sind, was dann auch deine zweite Frage beantworten würde.
Aber Vorsicht: du schreibst in deiner Frage "reguläre Ausdrücke aka Regex". Das ist falsch! Regex und reguläre Ausdrücke sind nicht dasselbe! Sie sind nur entfernt verwandt: die Syntaxen von Regex basieren zwar lose auf regulären Ausdrücken, aber die Semantik ist zum einen signifikant anders, zum anderen deutlich mächtiger. So sind reguläre Ausdrücke nicht-deterministisch, Regex dagegen sind deterministisch.
Ein Beispiel für den Nicht-Determinismus ist, dass für den Kleene-Operator * nicht definiert ist, wie oft er matcht, bei Regexen ist das dagegen definiert: üblicherweise matcht er soviel wie möglich ("greedy") und es gibt eine Variante (den *? Operator), die sowenig wie möglich matcht ("lazy").
Wie schon erwähnt, sind Regexen üblicherweise auch mächtiger als reguläre Ausdrücke. Das heißt, Regexen können Sprachen erkennen, die nicht von einer Typ-3-Grammatik beschrieben und einem endlichen Zustandsautomaten erkannt werden können. Zum Beispiel gibt es meistens sogenannte "Backreferences" (Rückverweise), mit denen in einer Regel auf frühere erkannte Fragmente zurückgegriffen werden kann.
(A|B|C)*\1erkennt alle Worte, die aus einer beliebig langen Folge von As, Bs und Cs bestehen, gefolgt von exakt derselben Folge. Dies ist keine Typ-3-Sprache, sie kann also nicht von einem regulären Ausdruck beschrieben werden.
Übrigens: es gibt eine ganze Menge Bequemlichkeits-Erweiterungen in Regexen, die sie nicht mächtiger machen als reguläre Ausdrücke:
- der + Operator: A+ ist lediglich dasselbe wie AA*, dadurch werden die Regexen also nicht mächtiger
- der ? Operator: A? ist dasselbe wie A|ε
- Zeichenklassen: [ABC] ist dasselbe wie A|B|C
- benannte Zeichenklassen: [[:alpha:]] ist dasselbe wie [ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz] ist dasselbe wie A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
- negierte Zeichenklassen: [^A]
Welche Sprachklasse Regexen erkennen können, ist meistens nicht exakt definiert und ist schwer zu sagen, da oft die Semantik von Regexen nicht exakt formal definiert ist, sondern von der Implementierung abhängt. Außerdem gibt es nicht die Definition von Regexen, fast jede Regex-Implementierung hat ihre eigenen Erweiterungen, ihre eigene Syntax, ihre eigene Semantik. Zum Beispiel haben Perl-Regexen eine andere Syntax und Semantik als Ruby-Regexen. Und selbst innerhalb von Ruby gibt es massive Unterschiede zwischen Ruby 1.8 und Ruby 1.9.
Eines kann man mit ziemlicher Sicherheit sagen: praktisch jede Regex-Implementierung erkennt weitaus mehr als nur die regulären Sprachen, weswegen es eigentlich vollkommen unpassend und irreführend ist, sie als reguläre Ausdrücke oder regular expressions zu bezeichen. (Larry Wall, der Erfinder und Diktator von Perl, hat deswegen verfügt, dass in Zukunft nur noch von "Regexen" gesprochen werden darf, damit keine Verwirrung entsteht.) Ob Regexen jedoch alle Typ-2-Sprachen erkennen oder nur einige, oder ob sie gar mehr als die Typ-2-Sprachen erkennen, das hängt von der Implementierung ab, und ist praktisch nie vernünftig dokumentiert.
Ich habe zum Beispiel das unbestimmte Gefühl, dass die Regexen von Ruby 1.9 Turing-mächtig sind, das heißt sie können alle Typ-0-Sprachen erkennen. Ruby-1.9-Regexp haben benannte Funktionen, Funktionsaufrufe, Entscheidung, Schleifen und Rückverweise. Ich vermute (kann es aber nicht beweisen), dass sie damit Turing-mächtig sind, was dann auch deine zweite Frage beantworten würde.
|
380 ● 4 |
