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.