Grundlagen der Theoretischen Informatik at Universität Koblenz-Landau

• Verknüpfung (Konkatenation):
  • w ◦ w′
  • assoziativ, oft geschrieben als ww′
• i-te Potenz:
  • w^0 = ε, w^i+1 = ww^i
• Reverse:
  • w^R = das Wort w rückwärts

• Konkatenation:
  • L ◦ M = {w ◦ w′ | w ∈ L, w′ ∈ M}
  • oft geschrieben als LM
• i-te Potenz:
  • L^0 = {ε},
  • L^i+1 := LL^i
• Reverse:
  • L^R = {w^R | w ∈ L}
• Kleene-Hülle
  • L^∗ = L^0 ∪ L^1 ∪ L^2 ∪ . . .
• Variante:
  • L^+ = LL^∗ = L^1 ∪ L^2 ∪ . . .

Menge RegΣ der regulären Ausdrücke (über Σ) ist definiert durch:

1. 0 ist ein regulärer Ausdruck
2. Für jedes a ∈ Σ ist a ein regulärer Ausdruck
3. Sind r und s reguläre Ausdrücke, so auch
   • (r + s) (Vereinigung),
   • (rs) (Konkatenation),
   • (r∗) (Kleene Stern)

Klammern können weggelassen werden, dann

• ∗ hat Vorrang vor Konkatenation
• Konkatenation hat Vorrang vor +

Eine Grammatik G über einem Alphabet Σ ist ein Tupel
G = (V, T, R, S)
Dabei ist
• V eine endliche Menge von Variablen
• T ⊆ Σ eine endliche Menge von Terminalen mit V ∩ T = ∅
• R eine endliche Menge von Regeln
• S ∈ V das Startsymbol

Die Dycksprache Dk ist die kleinste Menge, die folgende Bedingungen erfüllt:
1. epsilon ∈ Dk,
2. Falls w ∈ Dk, so auch xiw(xi)^_ .
3. Falls u, v ∈ Dk, so auch uv.

Klasse L_3, REG (regulär) = {L(G)|G ist rechtslinear}

Klasse L_2, CFL (kontextfrei) = {L(G)| G ist kontextfrei}

Klasse L_1, CSL (kontextsensitiv) = {L(G)|G ist kontextsensitiv}

Klasse L_1, CSL (beschränkt) = {L(G)|G ist beschränkt}

Klasse L_0, r.e. (aufzählbar) = {L(G)|G beliebig}

Klasse L (beliebige Sprache) = {L|L⊆ Σ^∗}

G = (V, T, R, S) rechtslinear <-> "füralle"(P → Q) ∈ R (P ∈ V und Q ∈ T∗ ∪ T^+ V) ==>

• Links eine einzelne Variable
• Rechts höchstens eine Variable
• Wenn rechts eine Variable steht, steht sie ganz rechts im Wort und das Wort enthält mindestens ein Terminalsymbol

G = (V, T, R, S) kontextfrei <-> "für alle"(P → Q) ∈ R (P ∈ V und Q ∈ (V ∪ T)^∗)==>

• Links eine einzelne Variable
• Die Prämisse macht keine Aussage, was der Kontext dieser Variablen ist(”kontextfrei“)
• Rechts steht etwas beliebiges

G = (V, T, R, S) kontextsensitiv <-> "für alle"(P → Q) ∈ R:

1. "es gibt" u, v, α ∈ (V∪T)^∗ "es gibt"A ∈ V (P = uAv und Q = uαv mit |α| ≥ 1)  oder S → ε
2. S nicht in Q ==>

• Eine Variable A wird in einen String α mit |α| ≥ 1 überführt
• Die Ersetzung von A durch α findet nur statt, wenn der in der Regel geforderte Kontext (u und v) vorhanden ist
• Das Wort wird nicht kürzer, außer bei ε ∈ L

G = (V, T, R, S) beschränkt <-> "füralle" (P → Q) ∈ R:

1. |P| ≤ |Q|, oder S → ε
2. S nicht in Q ==>

• Die Conclusio ist mindestens so lang wie die Prämisse, außer bei ε ∈ L.
• Das Wort wird nicht kürzer, außer bei ε ∈ L

Ein endlicher Automat ist ein Tupel
A = (K, Σ, δ, s_0, F)

• K endliche Menge von Zuständen,
• Σ endliches Alphabet,
• δ : K ×Σ → K Übergangsfunktion,
• s_0 ∈ K Startzustand
• F ⊆ K Menge der finalen Zustände.

Ein indeterminierter endlicher Automat (NDEA) ist ein Tupel A = (K, Σ,∆, I, F)

• K endliche Menge von Zuständen,
• Σ endliches Alphabet,
• ∆ ⊆ (K × Σ) ×K Übergangsrelation,
• I ⊆ K  Menge von Startzuständen,
• F ⊆ K Menge von finalen Zuständen.