0 Daumen
135 Aufrufe

Aufgabe:

Gegeben sei ein Alphabet Σ und ein DEA M der eine Sprache L ⊆ Σ∗ erkennt. Zu der Sprache L kann die gespiegelte Sprache ←− L betrachtet werden, die aus allen Wörtern w = b1b2...bn besteht, so dass das gespiegelte Wort ←−w = bnbn−1...b1 ein Element von L ist. Zeigen Sie, dass ein NEA existiert, der ←− L erkennt.

ich habe leider keine Ansatz wie ich die Aufgabe lösen soll, für Hilfe bin ich dankbar.

von

1 Antwort

0 Daumen
 
Beste Antwort
  1. Füge einen neuen Zustand \(q\) hinzu.
  2. Für jeden Endzustand \(q_F\) und jede Transition \(q_i\stackrel{a}{\to}q_F\), füge die Transition \(q_i\stackrel{a}{\to}q\) hinzu.
  3. Ersetze jede Transition \(q_i\stackrel{a}{\to}q_j\) durch die Transition \(q_j\stackrel{a}{\to}q_i\) (einschließlich der unter 2. hinzugefügten).
  4. Neuer Startzustand ist \(q\).
  5. Endzustand ist der Startzustand des DEA.

Der so konstruierte NEA erkennt die gespiegelte Sprache.

von 2,1 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community