Wahlpflichtthemen

2. Formale Sprachen (2)

Reguläre Sprachen - Definition

Als reguläre Sprachen bezeichnet man genau diejenigen Sprachen, die von endlichen Automaten akzeptiert werden. Zu jedem endlichen Automaten gibt es also eine reguläre Sprache und umgekehrt. Wir wollen uns im Folgenden auf die Beschreibung von regulären Sprachen konzentrieren. Eine allgemeine Untersuchung aller Sprachformen wäre hier zu umfangreich.

Äquivalent zu der oben angegebenen Definition, die sich auf Automaten bezieht, kann eine reguläre Sprache auch als reguläre Teilmenge von E^* definiert werden.

Reguläre Teilmengen oder Sprachen von E^*:

Es sei E ein Alphabet.
 

1. Ein regulärer Ausdruck ist ein Ausdruck einer bestimmten Form über der Zeichenmenge E È {È,*,Æ,l,(,)}.
    
   
2. Jeder reguläre Ausdruck a legt eindeutig eine ihm zugeordnete Sprache L(a) Ì E^* fest.
   Jede solche Sprache wird als reguläre Sprache oder reguläre Menge bezeichnet.
    
   
3. Formal sind reguläre Ausdrücke wie folgt festgelegt:
    
   
   1. Æ ist ein regulärer Ausdruck, und es gilt L(Æ) = Æ.
   2. l ist ein regulärer Ausdruck, und es gilt L(l) = {l}.
   3. Jedes Zeichen a Î E ist ein regulärer Ausdruck, und es gilt L(a) = {a}.
   4. Wenn a und a' regulär sind, dann sind es auch
      • die Vereinigung (a È a'), und es gilt L((a È a')) = L(a) È L(a'),
      • das Produkt (aa'), und es gilt L((aa')) = L(a)L(a'),
      • die Iteration (a*), und es gilt L((a*)) = L(a)*.

Reguläre Sprachen können als Wortmengen aufgefasst werden, die durch Anwendung der Operationen Vereinigung, Produkt und Iteration aus den Mengen Æ, {l} und {a} für jedes a Î E gebildet werden können.

[Index] [Zurück/Formale Sprachen 1] [Fortsetzung/Formale Sprachen 3]

Autor: Jürgen Dehmer
Letzte Änderung: