Reguläre Ausdrücke

Reguläre Ausdrücke sind rekursiv definiert:

• Die leere Zeichenkette $\varepsilon$ ist ein regulärer Ausdruck
• Für jedes $a\in{\cal L}$ ist das singleton $a$ ein regulärer Ausdruck
• Sind $x,y$ reguläre Ausdrücke, so ist die Verkettung $xy$ ein regulärer Ausdruck
• Sind $x,y$ reguläre Ausdrücke, so ist die Alternative $(x|y)$ ein regulärer Ausdruck
• Ist $x$ ein regulärer Ausdruck, so ist $(x*)$, also die Kleene'sche Hülle von $x$, ein regulärer Ausdruck

Die Semantik ist definiert als

• $\varepsilon\models\emptyset$
• ${\cal L}\ni a\models\{a\}$
• $x\models A$, $y\models B$, dann $xy\models AB$
• $x\models A$, $y\models B$, dann $(x|y)\models A\cup B$
• $x\models A$, dann $(x*)\models A*$

Die Abschlusseigenschaften deterministischer endlicher Automaten zeigen, dass jeder reguläre Ausdruck durch einen deterministischen endlichen Automaten dargestellt werden kann.

Umgekehrt zeigen wir, dass es zu jedem deterministischen endlichen Automaten einen äquivalenten regulären Ausdruck gibt. Die Idee ist simpel: Wir erlauben an Kanten reguläre Ausdrücke zu stehen, und entfernen sukzessiv Zustände und deren Kanten durch neue Kanten mit regulären Ausdrücken. Für einen Zustand $q_0$ gebe es kanten hinein von Zuständen $q_1,\ldots,q_k$, und kanten hinaus in Zustände $q_{k+1}, \ldots, q_l$, beschriftet mit regulären Ausdrücken $a_1,\ldots,a_l$, die am Anfang alle singletons sind, außerdem eventuell loops von $q_0$ nach $q_0$ für die Zeichen $b_1,\ldots,b_m$

              +-b1,...,bm-+
              |           |
              +----++-----+
                   ||
       (q1)--a1---+||+---a[k+1]--->(q[k+1])
                  ||||
                  V|V|
        ...       (q0)        ...
                  A  |
                  |  |
       (qk)--ak---+  +------al---->(ql)

Nun werden die Kanten vereinigt

       (q1)------a1 (b1|...|bm)* a[k+1]------>(q[k+1])
          |
          +------a1 (b1|...|bm)* a[k+2]------>(q[k+2])
          |
         ...
          |
          +------a1 (b1|...|bm)* al----------->(ql)
   
        ...
   
       (qk)------ak (b1|...|bm)* a[k+1]-------->(q[k+1])
          |
          +------ak (b1|...|bm)* a[k+2]-------->(q[k+2])
          |
         ...
          |
          +------ak (b1|...|bm)* al------------->(ql)

Sollten bereits Kanten von einem $q_i$ zu einem $q_j$ gehen, mit einem regulären ausdruck $r$, und müsste eine neue Kante mit dem regulären Ausdruck $s$ hinzufügen, so ersetzt man die Kante stattdessen durch $(r|s)$.

Wenn wir dies sukzessive weiterführen, haben wir am Ende einen Automaten mit nur noch einem Start- und einem Endzustand, und einem kompletten regulären Ausdruck auf der Kante zwischen beiden.