Kapitel 3 Reguläre Sprachen

Question 1

Definition Reguläre Sprache I

Answer 1

falls ein endlicher Automat diese Sprache erkennt

Question 2

Reguläre Operationen Arten

Answer 2

• Vereinigung
• Konkatenation
• Stern

Reguläre Sprachen sind unter diesen Operationen abgeschlossen

Question 3

Definition Reguläre Ausdrücke

Answer 3

Ein Wort R ist ein regul¨arer Ausdruck ¨uber dem Alphabet Σ, falls R von einer der folgenden Formen ist und keines der Symbole wie leeres Wort, leere Menge, |, Komma, Punkt, Stern, ()

Formen der Ausdrücke:

1. a, wobei a ∈ Σ,
2. leeres Wort,
3. ∅,
4. (R1 | R2), wobei R1 und R2 regul¨are Ausdrücke sind,
5. (R1 · R2) = (R1R2), wobei R1 und R2 regul¨are Ausdrücke sind, oder
6. (R∗1), wobei R1 ein regulärer Ausdruck ist.

Question 4

Definition Reguläre Sprache

Answer 4

falls ein endlicher Automat diese Sprache erkennt

ODER

Ein regulärer Ausdruck R über Σ repräsentiert eine formale Sprache.

so bezeichnet L(R) die Sprache von R:

1. a ∈ Σ repr¨asentiert {a},
2. Leeres Wort repr¨asentiert {leeres Wort}, die Sprache, die das leere Wort enthält,
3. ∅ repräsentiert ∅, die Sprache, die kein Wort enthält,
4. (R1 | R2) repr¨asentiert L(R1) ∪ L(R2),
5. (R1 · R2) repr¨asentiert L(R1) · L(R2) =(R1)L(R2),
6. (R∗1) repr¨asentiert (L(R1))∗.