Grail

Grail ist ein Tool, mit dem verschiedene Operationen auf regulären Ausdrücken und endlichen Automaten ausgeführt werden können. Es besteht aus einer Sammlung von Filtern, die hintereinander gehängt werden, um das gewünschte Resultat zu erhalten.

Grail wurde an der University of Western Ontario (Kanada) entwickelt (Grail Homepage).

Grail für Linux, Version 2.5 als RPM (für Redhat 7.3) und SRPM:

• grail-linux-2.5-0.i386.rpm (440k)
• grail-linux-2.5-0.src.rpm (535k)

Benutzung von Grail im Grundstudiumspool

Grail ist im Grundstudiumspool nur unter Linux zugänglich. Die Filter sind im Verzeichnis /usr/bin installiert (sollte normalerweise im Pfad $PATH enthalten sein).

Bei Problemen wenden Sie sich bitte an die Aufsicht im Rechnerpool oder an Holger Austinat.

Dokumentation von Grail

• User's Guide to Grail (Postscript)
• Manpages zu den einzelnen Filtern:
  • Entweder direkt aufrufen, z.B. man grail,   man fmtore, ...
  • Manpages im HTML-Format

Beispiele

Es folgen einige einfache Beispiele. In den einzelnen Kommandos stehen fm für "Finite State Machine" (= endlicher Automat), re für "Regular Expression" (= regulärer Ausdruck) und fl für "Finite Language" (= endliche Sprache). Die Kommandos sind jeweils rot geschrieben, die Grail-Ausgabe blau.

• Umwandeln eines regulären Ausdrucks in einen NFA:

  echo "(a+b)*(abc)" | retofm
  (START) |- 4
  0 a 1
  2 b 3
  0 a 0
  0 a 2
  2 b 0
  2 b 2
  4 a 1
  4 a 0
  4 a 2
  4 b 3
  4 b 0
  4 b 2
  1 a 6
  3 a 6
  4 a 6
  8 c 10
  6 b 8
  10 -| (FINAL)
  

• Umwandeln eines regulären Ausdrucks in einen NFA und wieder zurück in einen regulären Ausdruck:

  echo "(a+b)*(abc)" | retofm | fmtore
  (aa+ba*aa+aa*aa+a+(aa*a+ba*a+a+b)(ba*a+b)*ba*aa+(b+(aa*a+ba*a+a+b)(ba*a+b)*b)a)bc
  

• Vor dem Zurückwandeln den NFA deterministisch machen:

  echo "(a+b)*(abc)" | retofm | fmdeterm | fmtore
  (aa*b+bb*aa*b)(aa*b+bb*aa*b)*c
  

• Vor dem Zurückwandeln den NFA deterministisch machen und minimieren:

  echo "(a+b)*(abc)" | retofm | fmdeterm | fmmin | fmtore
  b*a(a+ba+bbb*a)*bc
  

• Die ersten (kürzesten) 10 Wörter der Sprache aufzählen:

  echo "(a+b)*(abc)" | retofm | fmenum -n 10
  abc
  aabc
  babc
  aaabc
  ababc
  baabc
  bbabc
  aaaabc
  aababc
  abaabc