Diskussion:Transitionssystem

Ein paar Worte zur Erläuterung:

Ein Quadrupel ist eine Struktur mit vier Argumenten. Im Klartext: Klammer auf, Argument Eins, Argument Zwei, Argument Drei, Argument Vier und Klammer zu.

Wenn TS vier Zustände enthält, dann ist S={S0,S1,S2,S3}

S0 ist die Menge aller Anfanstzustände. Naja, ein EA kennt eigentlich nur einen Anfangszustand, aber dafür ist ja eigentlich ein EA auch ein Quintupel, also eine Struktur mit fünf Argumenten, da u.a. die Menge der Endzustände eine Rolle spielt.

Das Alphabet enthält die Argumente, die ein Transitionssystem akzeptiert, um von einem Zustand in einen anderen (es kann auch der gleiche Zustand sein) auszulösen.

Dabei dürfen die Zustände nicht im Alphabet enthalten sein.

Im Gegensatz zu einem EA kann ein Transitionssystem unendlich viele Zustände enthalten, und ebenso im Gegensatz zum EA benötigt ein Transitionssystem auch keine Endzustände.

--Arbol01 22:49, 30. Nov 2004 (CET)

NEA vs. DEA

Gerade habe ich zum zweiten Mal im Artikel den Abschnitt "Nichtdeterministischer endlicher Automat" in "Deterministischer endlicher Automat" umbenannt und das Kapitel dahingehend abgewandelt. Der dargestellte Graph beschreibt nämlich keinen NEA sondern einen DEA. Manche Defintionen verwenden den Ansatz, daß NEA eine Obermenge aller DEA ist (was aber angesichts der Äquivalenz sowieso hinfällig ist), insofern wäre die Bezeichnung NEA hier zwar gerechtfertigt, aber im Rahmen einer Erklärung des Begriffs nicht sachdienlich und verwirrend, da die Besonderheit eines NEA in Abgrenzung zum DEA nicht ersichtlich ist. Diese Besonderheit eines NEA ist nämlich, daß er mehrere Übergänge in verschiedene Zustände unter dem gleichen Input zuläßt. Die Benennung des Bildes ist somit je nach Definition eines NEA sachlich falsch oder zumindest verwirrend. Ich bitte dies bei weiterer Bearbeitung zu berücksichtigen. --chris 論 11:30, 2. Dez 2004 (CET)

Moment: Ja, ein NEA läßt von einem Buchstabe des Alphabets mehrere Übergänge zu verschiedenen Zuständen zu. Die Definition eines DEA ist aber strenger: wenn ein EA ein Alphabet {a,b} besitzt, muß von jedem Zustand mit jedem Buchstaben ein Übergang existieren. Ich wiederhole: Es muß von jedem Zustand ein Übergang mit a und ein Übergang mit b existieren. Das ist aber in dem Beispiel nicht der Fall. Zweimal fehlt ein b-Übergang und einmal ein a-Übergang. --Arbol01 16:30, 2. Dez 2004 (CET)

Zur Ergänzung:

	a	b
S0	S1	-
S1	-	S2
S2	-	-

Wäre der EA ein DEA, dann dürften in der Übergangstabelle keine - vorkommen.

	a	b
S0	S1	0
S1	0	S2
S2	0	0
0	0	0

Das ist der zu dem oben beschriebenen NEA dazugehörige DEA. Er ist ein DEA, weil es zu jedem möglichen Übergang einen Zielzustand gibt. --Arbol01 16:38, 2. Dez 2004 (CET)

Du recht und unrecht. Richtig ist, dass eigentlich für jede Kombination von Zustand/Eingabe ein Übergang existieren sollte. Falsch ist, dass wenn das nicht der Fall ist, der Automat ein NEA ist. Also:

• Bei strenger Definition eines endlichen Automaten muss für jede Kombination von Zustand/Eingabe ein Übergang auf einen anderen Zustand existieren. Per konvention kann man die aber weg lassen (unvollständiger Automat), der entsprechende Vollständige Automat ergibt sich durch Einfügen eines Fangzustandes, so wie du das ja auch gemacht hast.

• Ein unvollständiger EA ist aber nicht notwendigerweise ein NEA: aus dem fehlen von Folgezuständen ergibt sich kein Indeterminismus, also keine Wahlmöglichkeit was der nächte Zustand sein muss. Ein Automat ist nichtderministisch, wenn er a) Epsylon-Übergänge hat, b) aus einem Zustand für die selbe Eingabe mehrere Folgezustände möglich sind oder c) es mehrere Startzustände gibt.

Mann kann das auch ganz gut sehen, wenn man versucht, den NEA per Potenzautomat in einen DEA zu verwandeln: es ändert sich nichts, der Potenzautomat ist identisch. Also ist der Automat bereits ein DEA.

So hab' ich das zumindest mal gelernt, und so habe ich es in der Literatur auch schon oft gesehen. Wenn du mir 'ne Quelle geben kannst, in der das anders steht, guck ich's mir gerne an.... -- D. Dÿsentrieb ⇌ 17:00, 2. Dez 2004 (CET)

S

So? Für mich ist es nicht identisch, denn ich bekomme noch einen Zustand dazu, egal wie du ihn nennen willst. Probiere es mal. --Arbol01 20:16, 2. Dez 2004 (CET)

Wie Duesentrieb schon erwähnt hat, macht das Hinzufügen bzw. Weglassen eines Null- oder Epsilonzustandes den Automat nicht indeterministisch, da er weiterhin durch eine (wenn auch partielle) Übergangsfunktion beschrieben werden kann. Das charakteristische Merkmal für den Indeterminismus eines Automaten ist aber die Tatsache, daß er nur durch eine Übergangsrelation beschrieben werden kann. --chris 論 21:17, 2. Dez 2004 (CET)

Den zusätzlichen Zustand bekommst du im Potenzautomaten nur, falls du darauf bestehst, für jedes Eingabezeichen einen Folgezustand anzugeben. Das ist nach dem Algorithmus für die Konstruktion des Potenzautomaten aber nicht notwendigt: man muss ja nur für jede Zustand/Eingabe-Kobination alle möglichen Folgezustände zusammenfassen. In diesem Fall ergeben sich einfach für manche Kombinationen gar keine Folgezustände, das ist durchaus erlaubt. Damit bleibt der Automat gleich. Dass die Übergangsfunktion vollständig sein muss wird nur dann verlangt, wenn man das für irgend einen Formalismus braucht, den man auf den Automaten anwenden will. Das wird meistens als o.B.d.A. angegeben das heisst als Beschränkung die durch entsperechende Umformulierung des Problems immer erfüllt ist. -- D. Dÿsentrieb ⇌ 22:32, 2. Dez 2004 (CET)

Für den DEA verlange ich die Vollständigkeit immer, für den NEA nicht. Meine vorerst letzte Antwort. Umzustimmen bin ich in dieser Sache nicht. --Arbol01 22:43, 2. Dez 2004 (CET)

Konfluenz (Informatik)

Hallo Leute!

könnt ihr mit dem Artikel Konfluenz (Informatik) was anfangen? Ich verstehe leider nichts. Offensichtlich ist Konfluenz eine Eigenschaft von Transitionssystemen, sollte er deshalb hier eingebunden werden? Oder mag ihn jemand überarbeiten und ergänzen? Viele Grüße, Kurt seebauer 15:00, 26. Mai 2005 (CEST)

hab mal einen Löschantrag gestellt. Wikipedia:Löschkandidaten/26._Juni_2005#Konfluenz_.28Informatik.29 --Kurt seebauer 13:29, 26. Jun 2005 (CEST)

Markierung

Hallo,

in der Definition des Artikels wird eine Markierung des Transitionssystems zwingend vorausgesetzt (auch wenn diese leer sein darf). Ich denke, man sollte auch unmarkierte Transitionssysteme in diesem Artikel behandeln oder wenigstens auf den Artikel über Reduktionssysteme verweisen. Dieser verweist bereits andersrum auf unmarkierte Transitionssysteme, die dann aber in diesem Artikel nicht behandelt werden.

Gruß (nicht signierter Beitrag von 77.191.142.154 (Diskussion) 10:14, 4. Jun. 2020 (CEST))