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

       (q1)--a1---+
                  |
                  V
        ...       (q0)
                  A
                  |
       (qk)--ak---+