Reguläre Mengen
|
über einem Alphabet A
|
|
|
Definition
|
induktiv
|
|
|
.1 {}
|
leere Menge
|
|
|
.2 {ε}
|
Menge mit dem leeren Wort
|
|
|
.3 {a}
|
für alle a ∈ A
|
|
|
.4 r1 ∪ r2
|
Mengenvereinigung
|
|
|
.5 r1 ⋅ r2
|
= { w1 ⋅ w2 | w1 ∈ r1, w2 ∈ r2 }
|
|
|
.6 r*
|
= r0 ∪ r1 ∪ r2 ∪ ... ∪ rn ∪ ...
|
|
mit
|
|---|
|
r0 = {ε}
r1 = r
r2 = r ⋅ r
rn = r ⋅ rn-1 für n>2
|
|---|
|
|
.7
|
die Bildungsgesetze .4 bis .6 dürfen nur endlich oft angewendet werden
|
|
|
|
Reguläre Mengen werden durch reguläre Ausdrücke repräsentiert.
|
|
Es gibt unterschiedliche reguläre Ausdrücke, die die gleiche reguläre Menge repräsentieren.
|
|
|
?
|
Beispiele?
|
|
|
Korrespondenz
|
Regulärer Ausdruck <--> Reguläre Menge
|
|
|
Korrespondenz
|
Regulärer Ausdruck <--> Endliche Automaten
|
|
|
Compilerbau & Formale Sprachen: Reguläre Ausdrücke
