4.3
 Reguläre Sprachen/Ausdrücke

Reguläre Sprachen und reguläre Ausdrücke (RA) 

• Die leere Menge ∅ und die Menge {ϵ} ist regulär. Als regulärer Ausdruck (RA) in JFLAP wird {ϵ} geschrieben als !
• Die Mengen {a₁},{a₂},...,{a_n} sind regulär. RA: a oder b
• Wenn L₁ und L₂ regulär sind, dann auch (L₁ ∪ L₂). RA: (A|B) (in JFLAP (A+B))
• Wenn L₁ und L₂ regulär sind, dann auch (L₁ ∙ L₂). RA: (AB)
• Ist L regulär, dann auch L^*. RA: (A)*

Wie kann man Optionalität ausdrücken?

Beziehung zwischen RA, DEA und formalen Sprachen 
Zu jedem regulären Ausdruck RA existiert mindestens ein EA, der die vom RA bezeichnete reguläre Sprache akzeptiert.

Zusammenfassung 

• Mit regulären Ausdrücken lassen sich alle regulären Sprachen beschreiben.
• Mit endlichen Automaten lassen sich alle regulären Sprachen erkennen.
• Jeder reguläre Ausdruck kann in einen endlichen Automaten verwandelt werden.