Teilbarkeit durch 3 mit regulären Ausdrücken

In Kapitel 4 wird beschrieben, wie man reguläre Ausdrücke finden kann, die die Teilbarkeit einer Binärzahl durch 3 ermitteln kann. In diesem Programm wird der Scanner-Generator flex(1) dazu verwendet die drei regulären Ausdrücke 

[1]    (0|1(01*0)*1)*
[2]    (0|(1(01*0)*1))*1(01*0)*
[3]    0*1(01*0|10*1)*01*

in endliche Automaten umzuwandeln. Die --trace erzeugt das File divisible.trace, welches die Definitionen des erzeugten NEA und DEA enthält. Die beiden Scripts trace2nfa.sh und trace2dfa.sh machen aus dem Trace-File zwei Dot-Files, mit denen das Graph-Visualisierungsverkzeug dot graphische Darstellung der Graphen erzeugen kann. Durch Anklicken der folgenden Bilder können leichter lesbare PDF-Versionen der Automaten erhalten werden.

NEA:DEA:

Im NEA kann man die drei unabhängigen aus den regulären Ausdrücken erzeugten Automaten erkennen, die über ε-Weichen erreichbar sind. Sie enden in den farbigen Akzeptierzuständen.

Im DEA sind nur noch Akzeptierzustände vorhanden, die drei Farben entsprechen den Farben der Akzeptierzustände des NEA. Der Automat ist nicht minimal, die Akzeptierzustände gleicher Farbe lassen sich zusammenlegen, so dass der aus Kapitel 1 bekannte DEA für durch drei teilbare Binärzahlen entsteht.

Files:

Ganzes Paket: divisible-1.0.tar.gz herunterladen.

Durch Anklicken des Files wird der Inhalt angezeigt:

  • Definition des Scanners mit regulären Ausdrücken: divisible.l
  • C-Code des Scanners erzeugt von flex(1) aus dem File divisible.l: divisible.tab.c
  • Trace-File, welches die Definition der endlichen Automaten enthält, die aus den regulären Ausdrücken generiert wurden: divisible.trace.
  • Hauptprogramm in C, enthält die main-Funktion, die ihrerseits den generierten Scanner in der Form der Funktion yylex() aufruft: divisible.c