0 Daumen
288 Aufrufe

Frage:

Sei PUMP die Menge aller pumpbaren Sprachen über einem fixierten
Alphabet Σ. Zeigen Sie, dass PUMP abgeschlossen unter Vereinigung, Konkatenation und Kleene Stern ist.

Code:

habe leider keinen Ansatz wie ich die Aufgabe lösen kann, für Hilfe bin ich dankbar.
von

1 Antwort

0 Daumen
Sei PUMP die Menge aller pumpbaren Sprachen über einem fixierten
Alphabet Σ

Genauer gesagt ist PUMP die Menge aller Sprachen L über Σ, für die gilt:

Es gibt eine natürliche Zahl n (genannt Pumpingzahl), sodass sich jedes Wort z ∈ L mit |z| ≥ n so in z = uvw zerlegen lässt, dass

  • |uv| ≤ n
  • v ≠ ε
  • uviw ∈ L für alle i ∈ ℕ

Seien L1, L2 ∈ PUMP.

PUMP abgeschlossen unter Vereinigung

Verwende die größere der beiden Pumpingzahlen als Pumpingzahl von L1 ∪ L2.

Konkatenation

Verwende die Pumpingzahl von L1 als Pumpingzahl von L1L2.

von 3,3 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community