0 Daumen
73 Aufrufe

Aufgabe:

Beweist oder widerlegt folgende Aussagen:
1. Für alle formalen Sprachen L1, L2 und L3 gilt:
(L1 ∩ L2) · L3 = (L1 · L3) ∩ (L2 · L3).
2. Für jeden NEA A mit n Zuständen gilt: Falls L(A) !=(nicht gleich) ∅, dann gibt es ein w ∈ L(A) mit |w| ≤ n − 1.
3. Seien L1 und L2 zwei reguläre sprachen über dem Alphabet Σ, dann ist L1∪L2 auch regulär.
4. Für alle formalen Sprachen L1, L2 gilt: wenn L1 ⊆ L2*, dann L1*.L2* = L2*.

von

1 Antwort

0 Daumen
  1. Gilt nicht. Finde ein Beispiel für

            (L1 · L3) ∩ (L2 · L3) ⊄ (L1 ∩ L2) · L3.

  2. Gilt. Ein w ∈ L(A) mit |w| ≥ n kann nur dann akzeptiert werden, wenn man im Kreis gelaufen ist.
  3. Gilt. Überlege dir, wie ein geeigneter ε-NEA aussehen könnte.
  4. Gilt. Wenn L1 ⊆ L2* ist, dann ist auch L1* ⊆ L2*.
von 4,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community