Benutzer-Werkzeuge
se:automatentheorie
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:automatentheorie [2008-12-01 14:54] stefan |
se:automatentheorie [2008-12-01 15:04] stefan |
||
|---|---|---|---|
| Zeile 45: | Zeile 45: | ||
| * S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich | * S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich | ||
| * δ(s<sub>i</sub>, x<sub>j</sub>) → S<sub>k</sub> (Folgezustände zu s<sub>i</sub>, leere Menge, ein oder mehrere Zustände) | * δ(s<sub>i</sub>, x<sub>j</sub>) → S<sub>k</sub> (Folgezustände zu s<sub>i</sub>, leere Menge, ein oder mehrere Zustände) | ||
| + | |||
| + | ==== Überprüfung, ob NEA und DEA äquivalent ==== | ||
| + | - Konstruiere zu gegebenem DEA einen äquivalenten NEA (direkt erfüllt, da jeder DEA schon ein NEA ist) | ||
| + | - Konstruiere zu gegebenem NEA einen äquivalenten DEA (akzeptiert die selbe Sprache) | ||
| + | * A = (X, S, S<sub>0</sub>, δ, F) → A<sup>d</sup> = (X, S<sup>d</sup>, s<sub>0</sub><sup>d</sup>, δ<sup>d</sup>, F<sup>d</sup>) | ||
| + | * S<sup>d</sup> := P(S) (alle möglichen Teilmengen von S) | ||
| + | * s<sub>0</sub><sup>d</sup> := S<sub>0</sub> (Menge der Anfangszustände des NEA ist **ein** Element von P(S)) | ||
| + | * δ(Q, x) := U<sub>q ∈ Q</sub>δ(q, x) | ||
| + | * F<sup>d</sup> := { Q ∈ S<sup>d</sup> | Q ∩ F ≠ ∅} | ||
| ===== ToDo ===== | ===== ToDo ===== | ||
| * Skript Herold lesen | * Skript Herold lesen | ||
se/automatentheorie.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
