Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


20. Pattern Matching



Übungen

  1. Geben Sie einen regulären Ausdruck für das Erkennen aller Stellen an, wo vier oder weniger aufeinanderfolgende Einsen in einer binären Zeichenfolge auftreten.
  2. Skizzieren Sie den nichtdeterministischen Automaten für das Pattern Matching, der das Muster (A+B)*+C beschreibt.
  3. Geben Sie die Zustandsübergänge an, die Ihr Automaten aus der vorangegangenen Übung realisieren würde, um ABBAC zu erkennen.
  4. Erläutern Sie, wie Sie den nichtdeterministischen Automaten modifizieren würden, um die nicht-Funktion (not) zu behandeln.
  5. Erläutern Sie, wie Sie den nichtdeterministischen Automaten modifizieren würden, um Joker (»?«) zu behandeln.
  6. Wie viele verschiedene Muster können mit Hilfe eines regulären Ausdrucks mit M oder-Operatoren und ohne den Hüllenbildungs-Operator beschrieben werden?
  7. Modifizieren Sie match derart, daß reguläre Ausdrücke mit der nicht-Funktion und Joker behandelt werden können.
  8. Zeigen Sie, wie eine Beschreibung eines Musters der Länge M und eine Text-Zeichenfolge der Länge N konstruiert werden können, für die die Laufzeit von match möglichst groß ist.
  9. Implementieren Sie eine Variante von match, die das im Beweis von Eigenschaft 20.1 genannte Problem vermeidet.
  10. Geben Sie den Inhalt der deque bei jeder Entnahme eines Zustands an, wenn match benutzt wird, um den Beispiel-Automaten aus diesem Kapitel mit der Text-Zeichenfolge ACD zu simulieren.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]