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: Reguläre Ausdrücke
