Zeigen Sie, dass ein NEA existiert, der ←− L erkennt.

Question

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.

Answer 1

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.