Wie funktionieren DEA-Automaten?
Hallo, ich habe die Aufgabe einen DEA-Automaten als Diagramm zu zeichnen.
Das Alphabet
ist gegeben. Die Aufgabe lautet einen Automaten als Diagramm zu erstellen, dessen Sprache als
definiert ist.
Wäre folgendes Diagramm eine Lösung für diese Aufgabe?
Zusätzlich habe ich noch die Frage ob DEA-Automaten Turing-Maschinen sind. Und sind NEA-Automaten auch Turing-Maschinen oder sind Turing-Maschinen noch mal etwas anderes? Ich bedanke mich für eure Hilfe.
1 Antwort
Wäre folgendes Diagramm eine Lösung für diese Aufgabe?
Ja, zumindest wenn q0 der Startzustand sein soll und ihr 0 als natürliche Zahl betrachtet (denn dein DEA akzeptiert auch das leere Wort).
Zusätzlich habe ich noch die Frage ob DEA-Automaten Turing-Maschinen sind. Und sind NEA-Automaten auch Turing-Maschinen oder sind Turing-Maschinen noch mal etwas anderes?
Turing-Maschinen, DEAs und NEAs sind erst einmal alles unterschiedliche Dinge.
Aber:
Jeden NEA kann man in einen DEA "transformieren". Genauer gesagt kann man aus jedem NEA einen DEA konstruieren, der exakt dieselbe Sprache akzeptiert.
Außerdem kann man jeden DEA in eine Turing-Maschine transformieren. Damit kann man dann natürlich auch jeden NEA in eine Turing-Maschine transformieren.
Somit kann man, wenn man unbedingt möchte, DEAs und NEAs als Turing-Maschinen auffassen.
Umgekehrt ist das allerdings nicht so: Es gibt Turing-Maschinen, die sich nicht in DEAs transformieren lassen.
Gewissermaßen ist "Turing-Maschine" der allgemeinste Begriff eines Automaten, den wir haben: Jede Sprache, die von irgendeinem Automaten akzeptiert wird, wird auch von einer geeigneten Turing-Maschine akzeptiert (das ist zumindest die gängige Annahme).
DEAs und NEAs hingegen sind sehr spezielle Automaten. Die von ihnen akzeptierten Sprachen sind relativ simpel - man nennt sie "reguläre Sprachen". Wie gesagt, man kann sie auch als Turing-Maschinen auffassen, aber meist hat man keinen Grund dazu.
Es gibt auch noch weitere Automat-Konzepte. Z.B. Kellerautomaten sind allgemeiner als DEAs, aber nicht so allgemein wie Turing-Maschinen.
Am besten guckst du dir mal ein Video an, wie Turing-Maschinen funktionieren, eigentlich sind die ein ganz cooles Konstrukt (auch wenn man nie im Leben damit programmieren wollte ;))
Vielen Dank für die Hilfe. Ja, dass man NEAs in DEAs transformieren kann in dem man mehrere Übergänge als einen neuen Zustand betrachtet weiss ich. Ich dachte nur 'Turing-Maschine' ist nur ein anderes Wort für 'Automat'. Aber demnach muss ich mir das noch mal genauer ansehen.