Was sind Automaten?

Bei der Suchen von Textmustern wird der Regulärer Ausdruck in einen sogenannten Automaten umgewandelt. Diesen Automaten kann man sich bildlich als Labyrinth vorstellen, mit Sackgassen, eventuell mehreren Wegen zu den Ausgängen - die sich auch kreuzen können - oder nur einem einzigen Ausgang. Jede Kreuzung (im Automaten sind das Knoten) werden durch die Richtung (Kanten) bestimmt. Dabei gehen von einem Knoten beliebig viele Kanten ab, aber keine mit der gleichen Bezeichnung (DEA: endlicher Automat).
Damit wäre die Reihenfolge der zu suchenden Zeichenkette eindeutig festgehalten.

Hier nun eine abschließende Aufgabe mit der Arbeit mit Automaten...
Dieses Projekt enstand im Rahmen eines Beleges im Fach Künstliche Intelligenz für das Studium der Technischen Informatik an der FHTW-Berlin.

Aufgabe

Schreiben Sie ein Programm, das einen regulären Ausdruck in Grail-Notation einliest und dann in einen NEA ohne Epsilonkanten ausgibt.

Das Programm muss folgende Teilfunktionen realisieren:

Mit normierten Automaten geht es am Einfachsten.
Verkettung zweier Automaten (im einfachsten Fall für die Konkatenation ab). Dazu werden alle Endknoten des ersten Automaten mit den Anfangsknoten des zweiten Automaten verknüpft.
Odern zweier Automaten (im einfachsten Fall für den Ausdruck a+b). Dazu werden alle Anfangsknoten des ersten Automaten mit den Anfangsknoten des zweiten Automaten verknüpft. Dies gilt sinngemäß auch für die Endknoten.
Sternen eines Automaten (im einfachsten Fall für den Ausdruck (a)∗). Dazu werden die Endknoten über Epsilonkanten mit den Anfangsknoten verknüpft.
Dazu muss der eingegebene regulärer Ausdruck in seine Bestandteile zerlegt werden, um die obigen Funktionen einsetzen zu können.

Beispiel 1 - RegEx

Ein Regulärer Ausdruck könnte so aussehen:

(((ab+cd+(ef+gh)*+ij)kl+mn))

Daraus wird der Automat generiert:
(START) |- 2 2 a 3 2 c 5 2 e 6 2 g 8 2 m 11 3 b 4 4 ~ 7 5 d 4 6 f 7 7 -| (FINAL) 7 i 9 7 k 10 7 ~ 2 7 ~ 4 8 h 7 9 j 7 10 l 7 11 n 7

... dann werden die Epsilon-Schleifen entfernt:
(START) |- 2 2 a 3 2 c 5 2 e 6 2 g 8 2 m 11 3 b 4 4 -| (FINAL) 4 i 9 4 k 10 4 ~ 2 5 d 4 6 f 4 8 h 4 9 j 4 10 l 4 11 n 4

... und letzlich die Epsilon-Ketten entfernt:
(START) |- 2 2 a 3 2 c 5 2 e 6 2 g 8 2 m 11 3 b 4 4 -| (FINAL) 4 a 3 4 c 5 4 e 6 4 g 8 4 i 9 4 k 10 4 m 11 5 d 4 6 f 4 8 h 4 9 j 4 10 l 4 11 n 4

Beispiel 2 - Automat

Aus dem ursprünglichen Automat (eps0108.txt - Beispiel aus: "KI-Automat interaktiv"):
(START) |- 1 1 a 3 1 b 4 1 b 5 1 c 6 1 ~ 3 2 -| (FINAL) 2 a 7 2 b 8 2 b 9 2 d 10 3 ~ 4 4 a 11 4 ~ 2 4 ~ 5 5 ~ 1

... werden die Epsilon-Schleifen entfernt:
(START) |- 1 1 a 1 1 a 11 1 b 1 1 c 6 1 ~ 2 2 -| (FINAL) 2 a 7 2 b 8 2 b 9 2 d 10

... und dann die Epsilon-Ketten entfernt:
(START) |- 1 1 -| (FINAL) 1 a 1 1 a 7 1 a 11 1 b 1 1 b 8 1 b 9 1 c 6 1 d 10 2 -| (FINAL) 2 a 7 2 b 8 2 b 9 2 d 10

Ki-Automat interaktiv

Das gesamte Projekt wurde im Team erarbeitet (siehe Dokumentation).
Die folgende optimierte Implementierung in PHP ist mein Anteil:

>>> Ki - Automaten (Web)

Grafik erstellen

GraphViz (Terminal)

Für die Erstellung der Grafiken wurde GraphViz verwendet:
* https://graphviz.org (executable)

Die Installation (Linux):
$ sudo apt install graphviz

Download für Windows:
* https://graphviz.org/download/

So sieht die GV-Datei (regex_3_eps_3.gv) vom Beispiel 1 aus:
digraph finite_state_machine { rankdir=LR size="8,5" node [shape=doublecircle] 2 4 node [shape=circle] 2 -> 3 [label=a] 2 -> 5 [label=c] 2 -> 6 [label=e] 2 -> 8 [label=g] 2 -> 11 [label=m] 3 -> 4 [label=b] 4 -> 3 [label=a,color=green] 4 -> 5 [label=c,color=green] 4 -> 6 [label=e,color=green] 4 -> 8 [label=g,color=green] 4 -> 9 [label=i] 4 -> 10 [label=k] 4 -> 11 [label=m,color=green] 5 -> 4 [label=d] 6 -> 4 [label=f] 8 -> 4 [label=h] 9 -> 4 [label=j] 10 -> 4 [label=l] 11 -> 4 [label=n] { rank=same; 3, 5, 6, 8, 11 } }
* siehe auch GraphViz pocket reference: https://graphs.grevian.org/reference