3.3 Beschreibender Mechanismus: Reguläre Ausdrücke
Als beschreibende Mechanismen lösen reguläre Ausdrücke Entscheidungsprobleme.
Entspricht ein Wort \(x\) einem regulären Ausdruck \(R \in RA_∑\), sagt man “\(x\) ist in der Sprache \(L(R)\)” oder mathematisch “\(x\in L(R)\)“.
Definition: Sprache eines regulären Ausdrucks
Es sei \(Σ\) ein beliebiges Alphabet. Für jeden regulären Ausdruck \(R \in RA_∑\) definieren wir die Sprache \(L(R)\) von \(R\) wie folgt:
- \(L(\emptyset)= \emptyset\)
- \(L(ε)= \{ε\}\)
- \(L(a) = \{a\}\) für \(a \in Σ\)
- \(L(R^*) = L(R)^*\) (d. h. \(L(R^*) = (L(R))^*\))
- \(L(RS) = L(R)L(S)\)
- \(L(R|S)= L(R) ∪ L(S)\)
Erläuterungen zur Definition
- \(L(\emptyset)=\emptyset\) beschreibt die leere Sprache.
- \(ε\) beschreibt die Sprache \(\{ε\}\)
- Jedes Symbol \(a \in Σ\) beschreibt die Sprache \(\{a\}\).
- \((R^*)\) beschreibt alle durch Konkatenation kombinierten Wörter, die von R beschrieben werden.
- \((RS)\) beschreibt die Wörter, die durch Konkatenation aus einem von \(R\) beschriebenen Wort gefolgt von einem durch \(S\) beschriebenen Wort
entstehen. - \((R|S)\) beschreibt alle Wörter, die entweder von \(R\) oder von \(S\) beschrieben werden.
Im Abschnitt über reguläre Ausdrücke haben wir einige Beispiele gesehen, welche wir nun mit der Notation der Sprache schreiben können.
Beispiele über \(Σ= \{a, b\}\)
- Die Sprache des regulären Ausdrucks \( R =a(b(ba)a)\) ist \( L(R) = \{abbaa\}\).
- Die Sprache des regulären Ausdrucks \( R =ab|baa\) ist \( L(R)) = \{ab, baa\}\).
- Die Sprache des regulären Ausdrucks \( R =(ab|baa)bb\) ist \( L(R) = \{abbb, baabb\}\).
- Die Sprache des regulären Ausdrucks \( R =(aa)^*b\) ist \( L(R) = \{w \in \{a,b\}|w = a^nb, \: n>0 \: gerade\}\).
- Die Sprache des regulären Ausdrucks \( R =((ba)|b)^*\) ist \( L(R) = \{w \in \{a, b\} |\) vor jedem \(.a\) steht mindestens ein \(b\}\).
- Die Sprache des regulären Ausdrucks \( R =ab|baa\) ist \( L(R) = \{ab, baa\}\).
- Die Sprache des regulären Ausdrucks \( R =(bb)^*a^*b(ba)\) ist \(L(R)= \{a^mb^naba | m \geq 0 \: gerade, \: n \geq 0\}\).
- Die Sprache des regulären Ausdrucks \( R =0|(1|2|3|…|9)(0|1|2|…|9)^*\) ist \( L(R) = \mathbb{N}_{\geq 0} = \) Menge der natürlichen Zahlen in Dezimalschreibweise.
Die Definition der regulären Sprachen kennen wir vom letzten Abschnitt. Wir halten hier eine Version fest, die reguläre Ausdrücke verwendet.
Definition: regulär
Eine Sprache \(A\) über dem Alphabet \(Σ\) heisst regulär, falls \(A = L(R)\) für einen regulären Ausdruck \(R ∈ RA_Σ\) gilt.
Somit sind alle Sprachen im obigen Beispiel regulär.
Hier haben Sie die Option Ihre Notizen zu diesem Abschnitt hochzuladen. Wir empfehlen eine sinnvolle Beschriftung z.B. 3_3_beschr_Notizen.