Endlicher Automat

freakC++

Hallo zusammen,

ist es nicht so, dass bei einem endlichen Automat von jeden Zustand jeder mögliche Übergang gemacht werden können muss. Angenommen ich habe zwei Übergänge "a" und "b". Dann muss von jedem Zustand ein Übergang "a" und ein Übergang "b" abgegeben. Andernfalls gäbe es eine nicht definierte Anweisung.

Ist das Bild beim Wikipedia Artikel "Endlicher Automat" dann nicht falsch?

http://de.wikipedia.org/wiki/Endlicher_Automat

Es wird eine Tür simuliert. Doch wenn man sich im Zustand "offen" befindet, gibt es keine Möglichkeit wieder den Überstand "öffnen" zu wählen. Praktisch macht es keinen Sinn, aber theoretisch muss es möglich sein. Der Übergang geht dann in denselben Zustand über.

Habe ich recht?

Vielen Dank
lg, freakc++

edit: Ich bin noch immer dafür, das Forum in "Mathe/Physik/Informatik" oder zumiondestens Theoretische Informatik umzubenennen

In Berechenbarkeitstheorie haben wir es so gelernt, dass man tatsächlich bei einem endlichen Automaten von jedem Zustand aus auch alle Übergangsmöglichkeiten angeben muss.

Andererseits wurde in einer anderen Vorlesung behauptet, dass bei einer Eingabe, für die es für den Zustand keinen Übergang gibt, gar nichts geschieht.

Wird wohl einfach Definitionssache sein.

Das ist das Problem, wenn man ein Unregistrierter ist: Man kann seine Beiträge nicht editieren.

Mir fiel dazu noch ein: In Berechenbarkeitstheorie hatten wir das Delta als Funktion definiert, so wie es im Wikipedia-Artikel auch steht. Für den Fall müsste m.M.n. tatsächlich für jede Eingabe für jeden Zustand ein Übergang existieren, da die Funktion sonst nicht wohldefiniert wäre.

In der anderen Vorlesung war das Delta als Menge von Tripeln definiert. Ist ein Tripel nicht in der Menge enthalten, ist dieser Zustandsübergang mit Eingabe Omega gar nicht erst erlaubt.

Da im Wikipediaartikel aber die Definition mit Delta als Übergangsfunktion angegeben ist, würde ich sagen, dass das Bild im Artikel mathematisch tatsächlich nicht korrekt ist.

freakC++ schrieb:

edit: Ich bin noch immer dafür, das Forum in "Mathe/Physik/Informatik" oder zumiondestens Theoretische Informatik umzubenennen

Haha. Mach doch mal nen Thread in Forentechnik auf, soweit ich weiss ist niemand dem Umbenennen von Foren grundsätzlich abgeneigt

(das Forum hieß bis vor ner Weile nur "Mathematik")

freakC++

Danke für die Hilfe. Dann hatte ich ja recht..höhö! Außerdem wären bei einem Zustandsdiagramm dann einige Zellen leer also NULL und das ist nie gut.

Also: Liebe Wikipedia-Freiwillige, bitte ändert das Bild, damit arme Schüler wie ich, nicht darauf reinfallen

lg, freakC++

freakC++

TravisG schrieb:

freakC++ schrieb:

edit: Ich bin noch immer dafür, das Forum in "Mathe/Physik/Informatik" oder zumiondestens Theoretische Informatik umzubenennen

Haha. Mach doch mal nen Thread in Forentechnik auf, soweit ich weiss ist niemand dem Umbenennen von Foren grundsätzlich abgeneigt

(das Forum hieß bis vor ner Weile nur "Mathematik")

Werde ich mal machen, aber ich habe in Erinnerung, dass sich jemand kritisch dagegen ausgesprochen hat.

Zeus

freakC++ schrieb:

Also: Liebe Wikipedia-Freiwillige, bitte ändert das Bild, damit arme Schüler wie ich, nicht darauf reinfallen

lg, freakC++

Das Bild ist nicht falsch.

Bashar

Woher weiß man, ob die Zustandsübergangsfunktion partiell ist oder ob sie für nicht angegebene Übergänge in den selben Zustand zurückführt? Anhand des Bildchens gar nicht.
Ersteres macht sich ganz gut für lexikalische Scanner, es sei denn man hat Lust, einen expliziten Fehlerzustand mit aufzumalen. Alles eine Frage der Definition, wie schon gesagt.

freakC++

Begründung?

Ein endlicher Automat ist nur dann wirklich endlich, wenn für jeden Übergang alle Eingaben definiert sind.

2.) Automaten können auch Akzeptoren sein und beispielsweise ein Wort auf Richtigkeit prüfen. Wenn das Wort richtig ist, gehört es dann einer bestimmen Grammatik oder einer bestimmen Sprache an?

Bashar

freakC++ schrieb:

Begründung?

Wofür? Dass es Definitionssache ist? [Edit: Sorry, dachte das wäre auf mich bezogen gewesen.]

Ein endlicher Automat ist nur dann wirklich endlich, wenn für jeden Übergang alle Eingaben definiert sind.

Kreative Auslegung. Das "endlich" bezieht sich auf die endlich vielen Zustände. Ein Kellerautomat hat beispielsweise unendlich viele mögliche Zustände.

2.) Automaten können auch Akzeptoren sein und beispielsweise ein Wort auf Richtigkeit prüfen. Wenn das Wort richtig ist, gehört es dann einer bestimmen Grammatik oder einer bestimmen Sprache an?

Einer Sprache. Ein Wort kann nicht einer Grammatik angehören.

freakC++

Bashar schrieb:

Wofür? Dass es Definitionssache ist? [Edit: Sorry, dachte das wäre auf mich bezogen gewesen.]

Das war auf Zeus gezogen. Dein Eintrag kam kurz danach.

Bashar schrieb:

Kreative Auslegung. Dass "endlich" bezieht sich auf die endlich vielen Zustände. Ein Kellerautomat hat beispielsweise unendlich viele mögliche Zustände.

Da hast Du mich missverstanden. Das sich das endlich auf die Anzahl der Zustände bezieht, war mir klar. Ein zusätzliches Kriterium für einen korrekten endlichen Automaten ist die Möglichkeit, von jedem Zustand aus eine Eingabe zu machen.

Bashar schrieb:

Einer Sprache. Ein Wort kann nicht einer Grammatik angehören.

Alles klar!

Also, ich bleibe dabei, dass das Wikipedia Bild falsch ist. Ihr konntet mich noch nicht überzeugen. Vor allem auf Zeus' Begründung bin ich gespannt. Dass es Definitionssache ist glauibe ich nicht. Es würde nämlich sonst strenggenommen keinen Sinn machen.

nocheinmitglied

Das was du meinst ist ein Deterministischer endlicher Automat

ein endlicher Automat muss nicht zwangsläufig deterministisch sein.

freakC++

Bei einem nichtdeterministischen Automat sind die Übergänge nicht eindeutig, aber es gibt auch von jedem Zustand die Möglichkeit jede Eingabe zu machen. Es ist eben nicht klar, wo man landet.

nocheinmitglied

freakC++ schrieb:

Bei einem nichtdeterministischen Automat sind die Übergänge nicht eindeutig, aber es gibt auch von jedem Zustand die Möglichkeit jede Eingabe zu machen. Es ist eben nicht klar, wo man landet.

nein, du kannst mehrere Transitionen vom gleichen Zustand mit gleichem Buchstaben haben, oder auch keine Transition mit diesem Buchstaben.

Hier http://de.wikipedia.org/wiki/Nichtdeterministischer_endlicher_Automat (bild ganz rechts)
von Zustand 4 aus kann man nur mit der 0 aus weiter, was auch bei einem NEA richtig ist.

Zeus

freakC++ schrieb:

Hallo zusammen,

ist es nicht so, dass bei einem endlichen Automat von jeden Zustand jeder mögliche Übergang gemacht werden können muss. Angenommen ich habe zwei Übergänge "a" und "b". Dann muss von jedem Zustand ein Übergang "a" und ein Übergang "b" abgegeben. Andernfalls gäbe es eine nicht definierte Anweisung.

Ist das Bild beim Wikipedia Artikel "Endlicher Automat" dann nicht falsch?

http://de.wikipedia.org/wiki/Endlicher_Automat

Es wird eine Tür simuliert. Doch wenn man sich im Zustand "offen" befindet, gibt es keine Möglichkeit wieder den Überstand "öffnen" zu wählen. Praktisch macht es keinen Sinn, aber theoretisch muss es möglich sein. Der Übergang geht dann in denselben Zustand über.

Habe ich recht?

Nein ein Endlicher Automat ist eine mathematische Struktur [5-Tupel (Σ, S, s0, δ, F) oder den 6 Tupel - vernachlässige ich.].
Σ, S und F sind Mengen. Dabei ist ihre konrekte Ausprägung nicht von Bedeutung.

Randbedinung für ein endlichen Automat sind:

die Menge der Zustände ist endlich.
von jeden Zustand ist das Erreichen von mindestes ein Endzustand möglich. [Sonst kommt der Automat nicht zu ende, sonder ist angehalten.]

Damit ist das Bild in dem Sinne falsch, weil du nicht erkennen kannst, was ist Startzustand, was ist Endzustand - also kannst du das Bild in zwei Versionen interpretieren.

Deine Ansicht in diesen Fall ist mir fremd. Wieso muss eine Überführungsfunktion zum selben Zustand geben. Normalerweise will man damit beliebige Wiederholen von einen Alphabet abbilden. Worin soll der theoretischen Sinn liegen?

Also ich kenne es so, dass nicht eingezeichnete/angegebene Zustandsübergänge implizit in einen "Fehlerzustand" führen. Also dass es einen zusätzlichen, nicht aufgeführten Zustand q gibt, in den alle nicht angegebenen Übergänge einlaufen; von q aus führt dann ein Übergang auf sich selbst für alle Symbole des Eingabealphabets. Weil q kein akzeptierender Zustand ist, wird das Wort nicht akzeptiert, sobald der "Fehlerzustand" einmal erreicht wird.

Michael E.

Zeus schrieb:

Σ, S und F sind Mengen. Dabei ist ihre konrekte Ausprägung nicht von Bedeutung.

Wohl aber ihre Mächtigkeit.

Randbedinung für ein endlichen Automat sind:
2) von jeden Zustand ist das Erreichen von mindestes ein Endzustand möglich. [Sonst kommt der Automat nicht zu ende, sonder ist angehalten.]

Definitionssache.

Es ist genauso wie fdfdg sagte.

Also ich kenne es so, dass nicht eingezeichnete/angegebene Zustandsübergänge implizit in einen "Fehlerzustand" führen. Also dass es einen zusätzlichen, nicht aufgeführten Zustand q gibt, in den alle nicht angegebenen Übergänge einlaufen; von q aus führt dann ein Übergang auf sich selbst für alle Symbole des Eingabealphabets. Weil q kein akzeptierender Zustand ist, wird das Wort nicht akzeptiert, sobald der "Fehlerzustand" einmal erreicht wird.

freakC++

Muss ein endlicher Automat eigentlich deterministisch sein? Eigentlich doch nicht.

Michael E.

Nein, muss er nicht. Aber die Menge der berechenbaren Probleme bleibt gleich.