Endlicher Automat

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.

freakC++

ok, danke

In gewisser Weise ist eine Uhr ein endlicher Automat und deterministisch.
Auch ein Auto ist ein endlicher Automat, aber man kann bremsen und und dabei das Radio aufdrehen, oder man kann bremsen und gasgeben gleichzeitig, bringt aber nicht so viel.
Auch ein Zauberwürfel ist ein endlicher Automat, aber deterministisch ist er aus "grammatikalischer" Sicht nicht.

Der Begriff, der hier noch fehlt, ist "Wahrscheinlichkeit".

Man kommt in der Ausgangsfrage möglicherweise nicht mehr so durcheinander, wenn man erstmal in binär umsetzt. Aber mache Wikipediaartikel sind auch öfter so Zusammenhangsarm dahergeschrieben, wie die üblich schlechten Studienscripts: Haupsache irgendetwas abladen.

Skym0sh0

stop mal jungs und mädels,

ein automat vom typ3 der chomsky hierarchie kann verschieden aussehen

- einmal wäre da der epsilon automat zu nennen, der keine eingabe braucht um den zustand zu wechseln
- dann gibt es den nicht deterministischen automaten, der mit 1 und derselben eingabe in verschiedene zustände wechseln kann
- dann gibt es den deterministischen automaten, der nur einen zustandswechsel mit einer eingabe haben kann

und dazu gibt es noch die eigenschaften der totalität und der minimiertheit (minimaler endlicher automat und totaler automat)

und wonach der TE fragt ist die totalität, und nein sie muss NICHT gegeben sein

wie gesagt eine tür kann man öffnen. und schliessen. aber eine offene tür kann man nicht öffnen und eine geschlossene tür kann man nicht schliessen

man kann aber alle automaten minimieren und auch alle automaten zu einem totalen automaten machen