Abschlusseigenschaften der regulären Sprachen

Definition

Sind $L_1$ und $L_2$ regulär dann sind

• Vereinigung $L_1\cup L_2$
• Komplement ${\overline{L}}_1$
• Schnitt $L_1\cap L_2$
• Konkatenation $L_1\cdot L_2$
• Kleene-Stern $L_1^{\ast }$
  regulär.

Die Laufzeit ist polynomiell.
Beim Komplement kann sie exponentiell sein.

Beweise

Vereinigung

Sprachen Abschluss unter Komplement

-> erst zu DEA

Link to original

Sprachen Abschluss unter Schnitt

siehe: Durchschnitt

Link to original