Diskussion:Endlicher Automat/Archiv

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Alte Beiträge

das wichtigste für ein lexikon fehlt, ist die ursache oder der nutzen des beschriebenen in leicht verständlichen worten, da die leser einer entyklopedie nicht immer ehemalige studenten höherer wissenschaften sind. Es wäre also schön folgende fragen am anfang zu beantworten. was macht man/welches problem löst man / anwendungsgebiete für / zu beschreiben.

Irgendwie fehlen die ganzen Verweise auf reguläre Grammatiken und die eigentliche Funktion eines Automaten, nämlich das Akzeptieren von Sprachen erzeugt durch eben diese Grammatik.

Wie hängen Deterministische endliche Automaten mit Turinmaschinen oder Kellerautomaten zusammen...

Das was hier "Akzeptor" genannt wird, kenne ich als endlichen Automaten.

Das was vorher beschrieben wird, habe ich im Studium als "Transduktor" kennen gelernt.

--zeno 20:21, 2. Feb 2004 (CET)

Der ganze Artikel sollte mal überarbeitet und strukturiert werden. Ist in einem ziemlichen Schwafel-Zustand momentan, da jeder seinen Senf dazugegeben hat. Endliche Automaten sind alle vorgestellten Modelle. --Coma 07:14, 3. Feb 2004 (CET)

Der Artikel kann stark verbessert werden. Ich müsste einige Highlights aus den Vorlesungen von Prof. Thomas hier rein setzen.

Mal ein paar Stichpunkte für mich oder jemand anders, wenn man mal Zeit hat:

  • Äquivalenz von Model und Maschinen erwähnen (endlicher Automat <-> regulärer Ausdruck, Stackautomat <-> kontextfreie Grammatik, Baumautomat <-> regulärer Baumausdruck/-sprache)
  • Äquivalenz von DEA, NEA, NEA mit Epsilon Übergängen, Wortautomat und die konstruktiven Beweise
  • NEA zu DEA via Potenzmengenkonstruktion (->kombinatorische Explosion)
  • Pumping Lemma (endlicher Automat -> endlich viel Speicher -> Wiederholung bei langen erkannten Strings)
  • Baumautomaten, Zusammenhang mit XML
  • Satz von Büchi, Elgi, Trachtenbroth (Zusammenhang endliche Automaten <-> Logik Model => Model Checking)
  • Modelierung von parallelen Prozessen
  • Zusammenhang mit Spieltheorie
  • Algebraische Monoide
  • Schöner Satz von Graphen endlicher Automaten mit LaTeX und xymatrix
  • Diverse Programme dafür
  • Hinweis auf die Standardnotation von Graphen endlicher Automaten
  • ein paar schöne Algorithmen dazu
  • Hinweis auf beide Automatenbücher von Hopcroft, Ullmann, evt. auch die Compilerbücher von Aho et al, Maurer/Willhelm, Güting
  • Hinweis auf ANTLR beim Parsen
  • Hinweis auf Softwarepaket vom Lehrgebiet von Prof. Thomas

-- Marc van Woerkom 16:31, 26. Aug 2004 (CEST)

Mir fallen gerade noch die Homomorphismen, Äquivalenzklassen usw. ein, tja und dann sind wir eigentlich auf einem hohem Level. Soll so ein Artikel das Expertenwissen widergeben, oder für jedermann verständlich sein?

Und bei den Mealy/Moore Automaten müsste man sich nochmal die Sicht der technischen Informatiker/Informationstechniker zu eigen machen, die evt. ein wenig von der Sicht der eher mathematisch geprägten theoretischen Informatiker abweichen könnte (taucht an der Stelle auf, wo es von Schaltnetzen -kein Gedächtnis- zu Schaltwerken geht) - auf jeden Fall mal beides checken.

--Marc van Woerkom 16:39, 26. Aug 2004 (CEST)

EAs <=> Reguläre Sprachen <=> Rechts-lineare Grammatiken <=> Links-lineare Grammatiken Die Äquivalenz muss auch noch rein.

--Marc van Woerkom 13:40, 27. Aug 2004 (CEST)

EA für's Parsen

Im Artikel steht:

Endliche Automaten spielen insbesondere beim Parsen von Dokumenten eine wichtige Rolle.

Das ist ja nicht so korrekt, die wichtigere Rolle spielen dort die Kellerautomaten, die den Tokenstrom gegen die Grammatik matchen. Die EAs bzw. regulären Ausdrücke helfen im wesentlichen beim Erzeugen des Token Streams aus dem Character Stream. --Marc van Woerkom 23:39, 14. Okt 2004 (CEST)

Grundsätzlich einverstanden; vielleicht dachte der Autor dieses Satzes einfach daran, dass man in Perl mit RegEx-Ausdrücken gut mit Dokumenten umgehen kann. Auf jeden Fall sollte der Satz aber angepasst werden. HannesH

leider wurde das parsen wieder mal mit dem gesamten kompilierungsprozess gleichgesetzt, was ja mal nicht stimmt. nur der scanner arbeitet mit DEAs, der parser mit PDAs. --141.76.8.100 7. Jul 2005 12:14 (CEST)

Deterministsisch endlicher Automat

Ich bin nicht einverstanden von der Änderung von genau auf höchstens. Warum? Weil dieses genau das beschreibt, was ein DEA ausmacht. Angenommen, ein DEA besitzt drei Zustände und ein Alphabet = {a,b}. Dann muß, um ein DEA zu sein, das Transitionsdiagramm in dieser Art aussehen:

a b
S0 S1 S2
S1 S1 S0
S2 S0 S2

Wenn in einem Transitionsdiagramm von mindestens einem Zustand nicht alle möglichen Transitionsmöglichkeiten vorhanden sind:

a b
S0 S1 S2
S1 S1 -
S2 - S2

Dann handelt es sich um einen NEA, und nicht um einen DEA. Das gleiche gilt, falls es mehr als einen Transitionsübergang zu wenigstens einem Buchstaben gibt:

a b
S0 S1 S2
S1 S1,S0 S2
S2 S1 S0,S2
Ich hab's anders gelernt, aber mein Herzblut klebt nicht daran. Wenn es keine mögliche Transition gibt, befindet sich der Automat (deterministisch) im Haltzustand, ohne zu akzeptieren. Dieser Haltzustand kann bereits vor Ende der Eingabe erreicht sein. Nichtdetermistisch heißt, dass es nach oder während der Abarbeitung der Eingabe mehrere mögliche Zustände geben kann. Das gibt es bei mehreren Übergängen pro Eingabebuchstabe oder bei ε-Übergängen (spontane Zustandswechsel ohne Eingabeabarbeitung).
Eigentlich wollte ich das genau nur an der richtigen Stelle platzieren. Vor meiner Änderung stand da
haben bei jedem Zustand genau für jeden Buchstaben ihres Alpabets eine Transition.
Gemeint ist vermutlich:
haben bei jedem Zustand für jeden Buchstaben ihres Alphabets genau eine Transition.
--Rat 23:05, 30. Nov 2004 (CET)
Genau --Arbol01 23:06, 30. Nov 2004 (CET)
Also in Hedtstück - Einführung in die Theoretische Informatik steht, dass ein deterministischer Automat genau ein Folgezustand hat oder der Automat vorzeitig stoppt (also kein Folgezustand). Auch wenn man mal die Bedeutung des Wortes "deterministisch" betrachtet, die nämlich aussagt, dass das Verhalten eindeutig ist, dann trifft das auch auf die Situation mit keinen Folgezustand zu. Bei keinem Folgezustand ist das Verhalten eindeutig definiert, es passiert nichts... Nur wenn es zwei mögliche Folgezustände gibt, dann kann man von nichtdeterministisch sprechen. Ich bin also ganz klar für eine Änderung diesbzgl. --TMP 15:35, 18. Jan 2006 (CET)

hab die optimierung des EAs mal konkretisiert, leider läuft das dann eher unter det. EA - bin mir nicht sicher, ob man nicht lieber dann diesen abschnitt in den DEA artikel verschieben sollte. --141.76.8.100 7. Jul 2005 13:01 (CEST)

Ich denke auch, dass Die Beschreibung besser zu dem DEA Artikel passt. Ich habe sie dort verschoben und unter EA den alten Text mit einem Verweis auf DEA Optimierung eingebaut. --TFW 09:45, 10. Jul 2005 (CEST)

Endliche Automaten malen

Interessiert vielleicht noch andere, die aus irgendwelchen Gründen Artikel oder so schreiben müssen, also habe ich es nach vorne auf den Artikel geschoben. Die Skizzen ersetze ich im Laufe der Woche, wenn ich mal meinen Arbeitsrechner zum Laufen gebracht habe. --Marc van Woerkom 23:11, 30. Nov 2004 (CET)

Bitte mehr Zusammenarbeit

Ich habe den Artikel ein wenig zurecht gestossen. Da ging einiges durcheinander und es waren m.M auch grobe Fehler drin. Was mich noch frustriert hat:

  • Automatentheorie ist eine primäre Domäne der theoretischen Informatik, auch wenn E-Techniker oder Linguisten hier sicher auch wichtige Beiträge geleistet haben. Und in der Informatik ist ein finiter Automat erstmal ein Einwegautomat ohne Ausgabe. Davon abweichend kann man gerne Erweiterungen vorstellen.
  • Wenn man hier schon die Axt anlegt, sollte es besser und nicht schlechter werden

Ich könnte jetzt noch weiter grummeln, aber ich lasse es mal. Insgesamt müssen wir noch einiges an Arbeit reinstecken und auch die anderen Artikel zu dem Thema mal überarbeiten. --Marc van Woerkom 00:35, 15. Apr 2005 (CEST)

Ich stimme dir voll und ganz zu, dass an dem Artikel (und anderen ähnlichen) noch viel gearbeitet werden muss. Werde ich mal schauen, ob ich da etwas machen kann. Allerdings bin ich mit der Linkauswahl nicht sehr glücklich, nachdem ich sie ja schon mal zusammengestutzt habe. Ich finde einfach, dass die Links der Uni Aachen inhaltlich sicher viel zu bieten haben, jedoch sehe ich dort das Problem, dass die Seiten unübersichtlich sind. Bei Model-Checking zb muss man bis zu 13 PDF's downloaden um die gesuchte Information zu finden. Bei den anderen Aacheneer Links bis zu 30 Folien und deswegen sehe ich diese nicht als sehr geeignet an. Der alte Xy-pic Link funktionierte nicht und auf die schnelle hab ich keinen Neuen gefunden (danke für die Suche Marc), und die Gastex-Beispiele würde ich immer noch weggeben, da sie ohne Umwege über die Gastex-Homepage erreicht werden können.
Das Auseinanderziehen der Weblinks für das Zeichnen finde ich auch nicht positiv, weil ich eine gesammelte Liste einfach sinnvoller halte. --ElRakı ?! 00:54, 15. Apr 2005 (CEST)
PS: Ich bin übrigens nicht nach der "5-Links-Regel" gegangen, sonst hätte ich alle Werkzeug-Links auch noch entfernen müssen.
Die Vorlesung vom Thomas ist vollständig in der Videofassung. Man hört dabei den Ton (ist ja eine Vorlesung) und sieht, wie er simultan auf den Folien Skizzen macht. 90min Vorlesung resultieren etwa in 40-50 MB Divx Video. Eine sehr gute Umsetzung einer Vorlesung für das Netz. Hat hier allerdings nur geklappt, weil der Prof. sehr gut vortrug und seine Assistenten die Technik im Griff hatten. --Marc van Woerkom 08:53, 15. Apr 2005 (CEST)
Die Visualisierung müsste eigentlich in einen eigenen Artikel, konkret für die EAs und dann noch einen für das allgemeinerere Problem automatisch zu einem gegebenen Graphen G=(V,E) eine Visualisierung zu generieren. Das ist eine eigene Disziplin, mit eigenen Konferenzen. Mal schauen, wann ich da mal zu komme. --Marc van Woerkom 09:00, 15. Apr 2005 (CEST)

Ich stöbere gerne in Wikipedia (zugegebenermaßen vorwiegend in dem englischsprachigen Teil) und finde immer wieder hervorragende Artikel. Leider gibt es auch viele Artikel, die trotz der offensichtlichen Bemühungen der Autoren völlig vorbei an dem Sinn eines Wikipediaartikels sowie an der Wahrheit bzw. Realität geschrieben werden. Der FSM Artikel hier gehört eindeutig in diese Kategorie.

Zum Sinn dieses Wikipedia Artikels: es soll versucht werden die Zustandsmaschine für einen interessierten Laien zu erklären, was ist das und wie wird das verwendet. Was sind die wichtigsten Merkmale. Zum Schluss würden ein paar Links auf weiter führende Literatur ausreichen. Statt dessen hat man den Eindruck, dass hier jemand die Automaten Theorie (mit fast 100% Fokus auf Spracherkennung) innerhalb eines Wikipedia Artikels ernsthaft erklären möchte.

Zum Wert (Wahrheit/Realität) dieses Wikipedia Artikels: Die Automatentheorie und die Zustandsmaschine wurden eingeführt in einer Zeit wo der Begriff „Informatik“ wahrscheinlich noch gar nicht existiert hat (das älteste Buch zu dem Thema, das ich persönlich kenne ist „Introduction to the Theory of Finite-state Machines“ vom Herr Gill, erschienen 1962). Wenn die Informatik sich dieser mächtigen, hervorragend beschriebenen und seit Jahrzehnten erfolgreich in der Praxis eingesetzten Methodik bedient, dann heiß es nicht, dass sich etwas wesentlich an der Theorie ändert. Das heißt, um die zwei wichtigsten Punkte zu nennen:

1. der Haupeinsatzgebiet für Zustandsmaschinen (der wahr Gedanke des Erfinders, der dahinter steht) die Modellierung des (Applikations-) Verhaltens ist
2. eine Zustandsmaschine Aktionen (als Ausgabe) kennt, bzw. eine Zustandsmaschine, die keine Aktionen benutzt, global gesehen ein Sonderfall ist (die meisten Zustandsmaschinen sind bis jetzt in der Hardwareentwicklung entwickelt worden, mittlerweile dicht gefolgt von Softwareentwicklung hauptsächlich in der Telekommunikations- und Maschinenbauindustrie)

Ich würde empfehlen den momentanen Artikel in „Spracherkennung in der Theoretischen Informatik“ umzubenennen und einen neuen, neutralen, und an die richtige Zielgruppe gerichteten (d.h. an die interessierte Laien) FSM Artikel zu schreiben. 217.236.197.132 22:37, 16. Mai 2005 (CEST)

Werkzeuge

  • AT&T FSM Library ™ [1]
  • AutoFSM [2]
  • Bandera [3]
  • Covered [4]
  • Dynamic Attachment Finite State Machine (DAFSM) [5]
  • Exorciser [6]
  • Finite State Kernel Creator [7]
  • Finite State Machine Editor [8]

Die Links gehören nicht in den Artikel, da WP keine Linkliste ist, siehe WP:WWNI mfg --ncnever 06:30, 21. Mai 2005 (CEST)

Artikel umgebaut

Ich habe den Artikel umgebaut, d.h. zunächst verallgemeinert (er war ganz auf Wort- und Spracherkennung ausgerichtet, was nur ein kleines Unterkapitel in dem Zusammenhang sein kann) und vereinfacht, d.h. lesbar für einen interesierten Laien gemacht. Das Erklären aller Deteils der Automatentheorie innerhalb eines Wikipediaartikels macht nicht viel Sinn und ist auch unmöglich. Ich denke es ist jetzt deutlich besser, vor allem verständlicher und allgemeiner als der alte Artikel, hoffe aber selbstverständlich auch auf Kommentare. Ein paar Details müssten sicher noch verbessert werden, viel erweitern würde ich es jedoch nicht mehr. Da sollte lieber die Referenzenliste (Literatur, Weblinks etc.) ausgebaut werden, falls jemand sich in die Materie wirklich vertiefen möchte. TFW 22:33, 14. Jun 2005 (CEST)

Erstmal muss ich dir stark widersprechen.
"Das Erklären aller Deteils der Automatentheorie innerhalb eines Wikipediaartikels macht nicht viel Sinn und ist auch unmöglich."
Dies sehe ich ganz und gar nicht so. In der Wikipedia sollten sicherlich möglichst viele Details der Automatentheorie zu finden sein, unmöglich ist es sicherlich nicht.
TFW 14:30, 15. Jun 2005 (CEST):In der Wikipedia können sicher viele Aspekte der Automatentheorie erklärt werden. Dennoch soll es nicht innerhalb eines Artikels versucht werden. Ansonsten vertrete ich eher die Ansicht, dass eine allgemeine Enzyklopedie kein Platz ist, um Akademische Themen in aller Ausfürlichkeit zu behandeln. Zu Automatentheorie gibt es unzählige Bücher, von denen wahrscheinlich kein einziges die ganze Thematik, sondern nur bestimmte, aus Sicht oder Interesse des Authoren wichtige, Aspekte, behandeln. Alleine zu Themen wie Validierung oder Optimierung der EA gibt es unmengen an Informationen in Form von Büchern, Papers und Webpublikationen. Man kann es nicht ernsthaft versuchen diese Informationen in der Wikipedia unterzubringen. Deshalb macht man überall Literatur- und Weblinkslisten. Schliesslich, wer liest eine Enzyklopedie? In der Regel sind das interessierte Laien, die sich kurz zu einem Begriff informieren lassen möchten. Der Fachmann, oder der der es werden möchte, kauft sich Bücher und schut vielleicht in die Enzyklopedie, um einen Startpunkt für seine Recherche zu haben, mehr nicht. Deshalb sollten die Artikel in Wikipedia vor allem verständlich sein und die Essenz des Themas korrekt wiedergeben.


Ich habe mir die beiden Versionen nicht im Detail durchgelesen, da mir jetzt Zeit und Lust dazu fehlt. Die Einteilung in Akzeptoren und Transducer halte ich für gewagt, da meines Wissens die Einteilung in deterministisch und nichtdeterministisch weiter verbreitet ist (es gibt auch Deterministischer endlicher Automat und Nichtdeterministischer endlicher Automat).
TFW 14:30, 15. Jun 2005 (CEST):es gibt Domänen, wo die Einteilung in DEA und NEA einen gewissen Sinn macht und entsprechend propagiert wird. In der Wikipedia soll jedoch die möglichst neutrale, d.h. allgemeine Betrachtungsweise angegeben werden. Nun spielt die Einteilung in DEA und NEA in mehr als 99% der Fälle in der Praxis gar keine Rolle. Ich will die einteilung in Akzeptoren und Transducer nicht überbewerten, aber aus praktischer Sicht zumindest macht sie viel mehr Sinn, da sie zwei ziemlich unterschiedliche Domänen einigermassen gut representiert: der Spezialfall der Wort- und Spracherkennung gegen den allgemeinen Einsatz der EA im Hard- und Software design (d.h. hauptsächlich Steuerungen, bzw. Verhaltensmodellierung). Während der Akzeptor keine Aktionen kennt und gewöhnlich "zu Ende" laufen wird, kennt der Transducer normalerweise kein Ende und beeinflußt die "Außenwelt" nicht nur mit allen seinen Zustenden, sondern vor allem mit seinen Aktionen.

Zusätzlich würde ich die längeren Erklärungen zu Moore Automat und Mealy Automat in deren Artikel packen.

TFW 14:30, 15. Jun 2005 (CEST):Die unterscheidung in Mealy und Moore sollte auf keinen Fall überbewertet werden, nur weil ich ein paar Sätze darüber geschrieben habe. Die Erfahrung zeigt jedoch (und die Suchanfragen in Google & Co.), dass dies mit Abstand, das gefragteste Thema im Bezug auf EA wohl ist. Was ist nun wirklich der Unterschied? Was ist besser? Warum? Deshalb gehören die zwei Modelle zu einem allgemeinen EA Artikel - möglichst einfach erklärt. Ein weiterführender Link sollte eine Vertiefung ermöglichen aber nur für die, die es sich wirklich antun wollen. Es gibt im übrigen viele Themen die in dem Artikel erwähnt sind, könnten aber zusätzlich in einem weiterführenden Artikel genauer behandelt werden (z.B. die Übergangstabelle, die ja viele interesante Variationen kennt)
Allgemein halte ich es sinnvoller, bei so großen Änderungen zuerst auf der Diskussionsseite eine Neueinteilung zu besprechen/vorzuschlagen, als direkt die Änderungen zu machen. --ElRakı ?! 10:58, 15. Jun 2005 (CEST)
TFW 14:30, 15. Jun 2005 (CEST):Ich habe mir die Diskussionsrunde angeschaut und habe gesehen, dass die meiste berechtigte kritik übersehen/überlesen wird. In solchen Situationen ist es oft die besste Vorgehensweise einfach etwas vorzubereiten (ich habe den Artikel sicher nicht in 5 Minuten entworfen und ich habe ihn auch nicht ohne Konsultierung anderer veröffentlicht) und sich dann der Kritik zu stellen. Unter Berücksichtigung der Tatsache wie unverständlich, chaotisch und in der Gesamtheit (neutrale Sicht!) falsch der alte Artikel war, glaube ich nicht, dass es jemand mit überzeugung verteidigen würde. Der neue Artikel beinhaltet auch ideen bzw. Textausschnitte aus dem alten und es kann sicher einiges noch verbessert werden. Es soll nur versucht werden, die allg. Regeln zu befolgen:
  • neutrale Sicht darstellen
  • Fokus auf die Essenz
  • Verständlichkeit für die Nicht-Fachleute

Hallo TFW, was ist denn gegen eine Verlinken und in Zusammenhang zur Übergeordneten Theorie stellen zu Anfang einzuwenden. Nennung und Verlinkung von überbegriff Automat (Informatik) und Fachgebiet Theoretische Informatik halte ich für wichtig. Wer nichts vom EA weiss, kann so wie der Artikel jetzt steht, gar nicht weiterkommen. -- Schewek 22:16, 15. Jun 2005 (CEST)

Ich finde diese Links wichtig und habe Deine gut gemeinte Intention nur falsch verstanden, da der Einführungstext, in dem Du die Links untergebracht hast, doch etwas merkwürdig war:
Ein Endlicher Automat ist ein Automat im Sinne der theoretischen Informatik. (!!!)
Ich habe gerade eben einen Link auf Automatentheorie unten in der Anleitung angelegt, da das Wort dort bereits verwendet worden ist. Von dort hat man (oder sollte man haben) dann Zugang zu allen Unterkapiteln der Automatentheorie, die in der Wikipedia untergebracht sind. Ich habe auch überhaupt keine Einwende gegen weitere Verlinkung von Begriffen, nur bei Inhaltsänerungen sollte man mit Bedacht vorgehen. -TFW 14:39, 16. Jun 2005 (CEST)
Mir ging es bei der Einfügung in erster Linie darum, den EA für den unbedarften Leser in einen Zusammenhang zu stellen. Das wird durch die Verlinkung weiter unten nicht geleistet.
TFW 11:18, 18. Jun 2005 (CEST): Das ist eine Ansichtssache, die schwer zu entscheden ist. Wenn ich mich frage, warum der "unbedarfte Leser" zu diesem Artikel gekommen ist, dann denke ich, es ist vor allem weil er wissen wollte was nun wirklich ein EA ist und nicht was für sonstige Ober- und Unterbegriffe dazu gehören. Diese Begriffe findet er wenn nötig in "siehe auch" Sektion, falls der Artikel sein Interesse so weit angeregt hat, dass er so weit gekommen ist. Dies wird aber nur dann der Fall sein, wenn der Artikel auch interessant, d.h. gut verständlich gewesen ist. Üblicherweise entscheidet sich alles ganz am Anfang des Artikels und deshalb sollten insbesondere die ersten Sätzte ansprechend sein. Das Zuordnen des EA zu der Automatentheorie gleich in dem Einführungstext ist aus meiner Sicht das Optimum aus "richtiger Fokus/Verständlichkeit" und "Aufstellen im richtigen Zusammenhang".

Ich habe auch ein Problem, als erste Definition "EA ist ein Modell des Verhaltens" zu lesen. Man könnte zur Annahme verleitet sein, es gehe um Verhaltensforschung. Solche übergeordneten Einordnungen sollten meiner Ansicht nach vor einer Detailbeschreibung stehen.

TFW 11:18, 18. Jun 2005 (CEST): Ich denke nicht, dass jemand, der den Begriff endlicher Automat liest, an etwas anderes als an (Computer-?) Technik denkt. Leider. Ich weiss nicht was für Hintergedanken der Erfinder des EA hatte. Sicher wollte er vor allem das Verhalten von Automaten verständlich modellieren. Er merkte aber sicher wie praktisch und der Art des menschlichen Denkens nahe sein Modell ist.
Vor zwei Wochen hat mich meine 14 jährige Nichte dabei "erwischt", wie ich ein Buch über Einsatz von Zusatandsmaschinen in Softwareentwicklung gelesen habe. Nun fand sie den Begriff "Zustandsmaschine" so interessant (?), dass sie unbedingt wissen wollte was das ist. Ich sagte ihr, es sei eine Möglichkeit Verhalten zu modellieren und als Beispiel baute ich für sie folgende Zustandsmaschine: sie (die Nichte) befand sich zunächst im Zustand "unwissend". Dank dem gezeigten Interesse ging sie in Zustand "zuhörend" über. Dank meiner Erklärung wechselte sie schliesslich in den Zustand "begeistert". Ich ersparte ihr weitere Details, um den Übergang zu "totale verwirrung" zu vermeiden. Das ganze hört sich vielleicht witzig an, hat aber einen ernsten Hintergrund: das EA Modell wird fast ausschliesslich in dem uns üblicherweise bekannten technischen Zusammenhang verwendet (und es ist sehr gut so z.B. für die Ingenieure). Wir sollten dieses Modell jedoch so nicht einschrenken (zumindest nicht in einer allgemeinen Enzyklopedie). Wer weiss wo und mit wieviel Erfolg dieses unglaublich mächtige Modell sonst eingesetzt werden könnte, um scheinbar sehr komplizierte Zusammenhänge zu "entknoten".
Vielleicht hilft diese doch ziemlich neutrale Erklärungsweise diese Technologie aus dem dunklen "Theorieschatten" herauszuholen und den ihr würdigen Platz in der Praxis endlich einzunehmen.

Vergleiche auch den Aufbau von Kellerautomat. (Idealerweise würde man EA, Kellerautomat und Turingmaschine alle einer Grobvorlage folgen lassen, aber das ist noch mehr Arbeit.) -- Schewek 15:58, 16. Jun 2005 (CEST)

TFW 11:18, 18. Jun 2005 (CEST): Ich denke der Automatentheorie Artikel wäre defür der besste Platz. Dieser gehört jedoch wirklich ebenfalls gründlich überbearbeitet.

JPG-Grafiken

Die JPG-Grafiken sehen ziemlich furchtbar aus, kann man die nicht als PNG neu erstellen? Dieser Hinweis:

Der StateWORKS Editor (engl.) ermöglicht das Zeichen von einzelnen EA sowie Systemen von EA, die dann als JPG Grafiken gespeichert werden können.

sollte auch raus, denn wenn die Software wirklich nur JPG erzeugen kann, kann sie ja nicht viel taugen. --Head Diskussion 18:10, 14. Jul 2005 (CEST)

Über den Geschmack kann man sich bekannterweise endlos streiten, obwohl ich zugeben muss, dass die "treppenformigen" Linien nicht ganz den heutigen Standards entsprechen. Vielleicht kann man diese Grafiken mit dem Tool auch besser generieren (?). Ich will mich Mal in einer freien Minute schlau machen. Für mich waren die technischen Aspekte viel wichtiger: nachdem ich die EAs "gezeichntet" habe, konnte ich sie auf Korrektheit testen. Die Entwicklungsumgebung ist in erster Linie dazu da, EAs und systeme von miteinander kommunizierenden EAs zu entwickeln, testen und ausführen. Das Exportieren der grafischen Darstellung ist nur ein netter Site-Effect und nicht die Hauptfunktionalität. Deshalb konnte ich sicherstellen, dass die dargestellten EAs vollständig und fehlerfrei sind. Der Verweis auf die Entwicklungsumgebung ist sinnvoll, weil es das einzige mir bekannte Werkzeug ist, um EAs (und systeme von EAs) zu bauen, testen und ausführen (ohne irgendetwas codieren zu müssen). -TFW 12:15, 16. Jul 2005 (CEST)
Kannst du (oder jemand anders) bitte mal überprüfen, ob man die Automaten im PNG- statt als JPG-Format ausgeben kann? Dann wären sie OK. --Head Diskussion 12:29, 21. Jul 2005 (CEST)
Habe mir die Zeit genommen, die Bildchen neu zu zeichnen und im PNG Format abzuspeichern. --Babakus 22:51, 29. Aug 2005 (CEST)

Aufrennung nach Disziplinen

Ich finde wir sollten den Artikel nach Disziplinen auftrennen. Ich habe die entsprechenden Vorlesungen der Elektrotechniker/Technischen Informatiker und die der Theoretischen Informatiker/Mathematik gehört, die zwar über das gleiche reden, aber unterschiedliche Gewichtungen am Thema haben. Und wer weiss, was die Computerlinguisten aus dem Thema machen..

Die jetzige Präsentation entspricht dem Fokus der Elektrotechniker/Technischen Informatiker/Kybernetiker, die näher an den Anwendungen sind, z.B. kann man ja diese Maschinen für die Modellierung von Schaltwerken oder Kommunikationsprotokollen verwenden. Daher der ganze Zoo von Maschinenmodellen mit endlichen Speicher, mal mit, mal ohen Ausgabe.

Die Theoretischen Informatiker schauen sich in der Theorie der formalen Sprachen mehr an, welche Modelle äquivalent sind und welche Sprachen erkannt werden können. Das gibt eigentlich einen ganz anderen Artikel.

--Marc van Woerkom 13:07, 29. Mär 2006 (CEST)

endlich?

Abb.1 Beispiel eines EA

Was ist das endliche an einem endlichen Automaten? Auf mich wirkt das Beispiel auf der rechten Seite unendlich. Die Tür ist mal auf, mal zu, aber richtig zu Ende ist dieser Prozess nie. --Abdull 12:58, 29. Jul 2006 (CEST)

Der „Speicher“ ist endlich. In diesem Beispiel genügt ein Bit, um den Zustand des Automaten zu repräsentieren (offen oder geschlossen). Eine Turingmaschine könnte man im Gegensatz dazu als unendlich bezeichnen, weil ihr ein unendlich langes Band zum Lesen und Schreiben zur Verfügung steht. --jpp ?! 20:53, 29. Jul 2006 (CEST)

--cyriz

endlich bezieht sich auf die Verarbeitung von Symbolen und daher auf die Anzahl der Zustände).

Die Sprache (also Strings) die ein Automat akzeptiert kann jedoch auch unendlich sein (bsp L = a*). Daraus können unendlich viele Strings erzeugt werden, aber jeder dieser Strings ist endlich.

Fehlt bei diesem Bild aber nicht der (hypothetische) Fall, dass eine bereits offene Tür erneut geöffnet wird bzw. eine geschlossene Tür erneut geschlossen wird. Der Zustand bleibt dabei zwar derselbe, aber diese Möglichkeit besteht und wäre denke ich zur bessere Verständlichkeit und zum Aufzeigen möglicher Varianten hilfreich?! --SoulProvider 19:37, 12. Feb. 2007 (CET)

Hallo, müsste es nicht umgekehrt heissen ? Im Zustand 2 geschlossen. !Eingangsaktion Tür öffnen! statt !Tür schließen! ? Oder verstehe ich da was falsch. Danke

Medwedew-Automaten

Neben Moore und Mealy gibts doch auch noch Medwedew-FSMs. Irgendiwe sind die rhier unter den Tisch gefallen oder so. Also wenn jemand so nen Statemachinezeichenprogramm hat, und weiss worums geht, bitte mal nen Medwedew-Automat hinzufügen. (nicht signierter Beitrag von 141.47.69.128 (Diskussion) )

Kann es sein, dass du Medwedjew-Automaten meinst? --jpp ?! 17:31, 6. Jun. 2007 (CEST)

Werkzeuge

Entbehrliche Liste von Tools.. oder wie ein Kommilitone sagen würde: Was soll die Scheisse eigentlich?

  • [state] method steed.net
  • AT&T FSM Library ™
  • AutoEdit
  • AutoFSM
  • Bandera
  • Covered
  • Dynamic Attachment Finite State Machine (DAFSM)
  • Exorciser
  • Finite State Kernel Creator
  • Finite State Machine Editor
  • Finite State Machine Explorer
  • FSMGenerator
  • FSA Utilities
  • JFLAP
  • jrexx-Lab
  • Kara
  • MATRIXx
  • Nunni FSM Generator
  • Petrify
  • Qfsm
  • Quantum-Leaps
  • Automaten IDE
  • Ragel
  • Stateflow
  • Statestep
  • StateWORKS
  • WhatOS
  • Xerox Finite-State Software Tools

--89.247.72.222 00:13, 27. Nov. 2007 (CET)

Weblinks

Die Weblinks müssten meiner Meinung nach ausgedünnt werden. Einige davon sind ungeeignet. --Trublu ?! 23:03, 18. Jul. 2007 (CEST)

Na jetzt siehts doch schon viel übersichtlicher aus ;-) --89.247.7.83 13:05, 27. Nov. 2007 (CET)

Rahmen oder Rahmenwissenschaften fehlen

Es fehlen Hinweise in welchen Disziplinen EAs behandelt werden und aus welcher wissenschaftlichen Sachlage heraus. (Der vorstehende, nicht signierte Beitrag stammt von 192.129.26.10 (Diskussion • Beiträge) 12:43, 26. Jan 2008) -- Complex 19:13, 13. Apr. 2008 (CEST)

Anzahl der Startzustände eines endlichen Automaten

Wenn auch sehr unüblich, so kann zumindest ein NEA meines Wissens definitionsgemäß durchaus mehrere Startzustände haben, siehe hierzu etwa auch den Artikel NEA. Eine Suche mit Google nach "mehrere Startzustände" NEA führt ebenfalls zu diversen ernstzunehmenden Quellen (u.a. Universitäten), die dies bestätigen.

Da der Artikel Endlicher Automat, der die NEAs ja mit abdecken sollte, im Abschnitt 'Das mathematische Modell' aber von nur einem einzelnen Startzustand spricht, bin ich nun etwas verwirrt...ist das ein Fehler im Artikel? -- Aves83 10:35, 21. Okt. 2008 (CEST)

wie zum beispiel hier dargelegt, gibt es nur bei NEA mehrere startzustände. gruß --Murkel (anmurkeln) 20:37, 23. Okt. 2008 (CEST)
Das hatte ich oben ja auch schon angemerkt. Mein Problem ist, dass die Möglichekeit mehrerer Startzustände bei bestimmten EAs (eben den NEAs) im Artikel nicht berücksichtigt wird. Daher eben meine Frage: Sollte die Möglichkeit im Artikel nicht erwähnt werden? Die aktuellen mathematischen Definitionen im Bereich Das mathematische Modell vermitteln in meinen Augen den Eindruck, dass EAs nur einen Startzustand haben können. --Aves83 21:45, 27. Okt. 2008 (CET)

Medwedjew-Automat

Im Artikel wird der Moore- und der Mealy-Automat erwähnt. Der Medwedjew-Automat fehlt. Grob gesagt, entspricht der Medwedjew-Automat einem Moore-Automat, die Ausgabe entspricht aber exakt dem Zustand, d.h. Γ = S. Ich fühle mich jedoch nicht berufen, den Artikel zu ändern, da meine Automatentheorie-Vorlesung zu weit zurückliegt.--Rotkaeppchen68 15:43, 16. Okt. 2009 (CEST)

Mealy-Grafik

Die Grafik zum Mealy-Automaten finde ich sehr schwer zu verstehen. Ich kenne das so, dass die Ausgabefunktion durch einen Schrägstrich getrennt hinter dem Eingangssymbol steht. Dadurch findet ich die Zuordnung leichter zu verstehen und den Unterschied zum Moore-Automaten deutlicher. Helmut Balzert verwendet es auch so in seinem Lehrbuch der Softwaretechnik.

Ich finde die Grafiken hier auch nicht so gut. Abbildung 1 ist doch eigentlich ein Moore Automat (der Ausgang steht unter dem Mittelstrich), steht aber nicht dran. Hier wird das Ausgangssignal außerdem "Eingangsaktion" genannt, was ich verwirrend finde. Viel verständlicher sind die Beispiele auf der Wikipedia Seite Moore-Automat. -- Cabfdb 21:38, 9. Dez. 2009 (CET)

Zustandstabelle in Artikeleinleitung

Zustandstabelle in Artikeleinleitung: Die horizontale Spaltenbezeichung ist meiner Ansicht nach ungewöhnlich. Normalerweise sind die Zustände auf den linken Spalten angeordnet und bezeichnen eine Zeile. Die Bedingungen (zumeist die Eingabe) in der oberen Spalte eingeordnet.

Quellen: http://www.mi.uni-koeln.de/c/mirror/f7alpha1.informatik.fh-muenchen.de/~schieder/programmieren-1-ws96-97/calculator.html#section_4_8_4

http://oszhdl.be.schule.de/gymnasium/faecher/informatik/automaten/uebergangstabelle.html

Momentan ist es nicht falsch, aber eben ungewöhnlich.... (nicht signierter Beitrag von 92.193.37.142 (Diskussion) 08:46, 11. Mär. 2011 (CET))

Artikel inkonsistent und fehlerhaft

Der Artikel bedarf der Überarbeitung.

Nur einige wenige Punkte die mir im überfliegen aufgefallen sind:

- Der Abschnitt "Klassifikation" bezieht sich auf Notation die erst im Abschnitt "Mathematisches Modell des EA" eingeführt wird.

- Die im Abschnitt "Klassifikation" vorgenommenen Bezüge auf Abbildungen sind teilweise konfus, unnötig kompliziert oder fehlerhaft. (Bsp: Automat in Abb3. kennt keine Eingabe E:, Die Existenz eines Motors zur Türsteuerung ist irrelevant)

- Abschnitt Mathematisches Modell: "Akzeptor (oder auch deterministischer Automat)" das sind zwei orthogonale Begriffe.

-- Bnord 09:17, 27. Apr. 2011 (CEST)

Mealy-Automat Beispiel

Der Mealy-Automat enspricht m.M.n nicht genau dem Moore-Automaten bzw. ist einfach ungenau formuliert. Ich schlage vor den Text folgendermaßen zu ändern:
Im Mealy-Modell werden Eingabeaktionen benutzt, d. h., die Ausgabe (Γ) hängt von Zustand (S) und Eingabe (Σ) ab (S × Σ → Γ). Das Beispiel in der Abbildung 4 zeigt einen Mealy-EA, der das gleiche Verhalten wie der EA im Moore-Beispiel aufweist. Im geschlossenen Zustand (1) wird bei Eingabe des Befehls "öffnen" der Motor zum Öffnen der Tür in Gang gesetzt, und in Zustand 2 gewechselt. In diesem Zustand wird abhängig vom eingehenden Befehl der Motor entweder in die eine oder die andere Richtung gestartet. Gibt in diesem Zustand der Sensor die Eingabe "Tür ist offen" oder "Tür ist geschlossen" wird der Motor gestoppt und in den entsprechenden Zustand gewechselt. Analog zu Zustand 1 ist in Zustand 3 die Tür geöffnet und der Befehl "schließen" iniziiert die Schließung. Dadurch, dass die Ausgabe (hier: Steuerung des Motors) nun nicht nur vom aktuellen Zustand, sondern auch von der Eingabe abhängt, werden weniger Zustände benötigt.
und die Abbildung durch diese zu ersetzen: http://i.imgur.com/cugNOJ4.png
Johnplusb (Diskussion) 21:38, 14. Dez. 2014 (CET)

Abgesehen von der Abb. für den Mealy Automaten ist noch mehr nicht in Ordnung. Auf die Idee, Moore und Mealy wären "gleichwertig" kann nur kommen, wer den zeitlichen Aspekt vernachlässigt. Tatsächlich belegt in getakteten digitalen Schaltungen jeder Zustand eine Mindestdauer (nämlich mindenstens einen Takt bzw. "clock"), dass zeitliche Verhalten unterscheidet sich daher grundlegend. (Auch bei mechanischen Automaten kann die Verweildauer in einem Zustand nicht unendlich klein sein.)
Hinzu kommt ein weiterer Aspekt: beim Moore Automaten wirkt sich die Eingabe nur indirekt auf die Ausgabe aus, während bei Mealy die Eingabe unmittelbar auf die Ausgabelogik durchgreift - dieser Aspekt spielt insbesondere bei der Entwicklung digitaler Schaltungen´eine wichtige Rolle. Diese Unterschiede sind der Grund für den im Artikel genannten gemischten Einsatz beider Modelle - für den es keine Veranlassung gebe, wären beide Modelle wirklich gleichwertig. --Burkhard (Diskussion) 18:30, 21. Feb. 2015 (CET)
@Johnplusb, Drahkrub: Ich finde das alles recht fragwürdig. Hierher bin ich gekommen über die WP:Grafikwerkstatt, da dort eine simple Anfrage aufgrund der Qullenlage hier noch schon fast ein halbes Jahr "unerledigt" ist. Warum soll denn jetzt plötlich die komplette Bezeichnung geändert werden, nach dem Artikel (auf den sich der Grafikersteller ja hier nur beziehen kann), ist von Motor allg. gar nicht die Rede, da nur ein Bsp. Die Grafik soll aber das allg. Schema darstellen. ↔ User: Perhelion  11:00, 31. Jul. 2015 (CEST)
Hi Perhelion - schön, dass sich nach so langer Zeit jemand meldet. Mir ist leider nicht ganz klar was genau Dir fehlt. Die Abb. beziehen sich auf ein Türsystem mit Motor und Sensoren wie im Fliesstext daneben beschrieben. Die Unvollständigkeit der Abb. 4 zum Mealy-Beispiel ist unmittelbar einleuchtend, es fehlt der Zustand in dem die Tür sich zwischen den Zuständen Auf bzw. Zu befindet, damit sind die hier verglichenen Moore- (Abb. 3) und Mealy Automaten nicht vergleichbar. Dass darüberhinaus die Existenz eines Motor in beiden Abbildungen unerwähnt bleibt, ist ein gemeinsamer Mangel, der sich aber auch durch eine verbesserte Bildunterschrift heilen liesse.
BTW: Literatur zum unterschiedlichen Verhalten von Moore und Mealy Automaten in digitalen Schaltungen:
  • Pong P. Chu: RTL Hardware Design using VHDL. Wiley Interscience, 2006. ISBN 9780471720921. Speziell zum Thema Kapitel 10, insbesondere 10.4: Moore machine versus Mealy machine.
Gruß, --Burkhard (Diskussion) 16:01, 7. Aug. 2015 (CEST)
Burkhard hat mich gebeten, hier mal rein zu schauen. Die Grafik Datei:Door_mealy_example_de.png habe ich nur nach Commons übertragen, sie stammt aber nicht von mir. Die Grafik ist für sich betrachtet nicht falsch, aber sie passt natürlich nicht zum Moore-EA. Daher ist es das Sinnvollste, eine inhaltlich bessere Grafik bei Commons einzustellen und im Artikel auf die neue Datei zu verweisen.
Der Vorschlag oben scheint mir auf den ersten Blick aber nicht das darzustellen, was der Moore-EA macht: Der Automat mit drei Zuständen erlaubt die Sequenz "(Öffnen; Motor+) (Schließen; Motor-) (Sensor offen; Motor stop)". Dagegen ist "aufmachen -> zumachen -> Sensor auf" beim Moore-Automaten nicht möglich. Davon abgesehen sollte das mit dem Motor in beiden Grafiken oder gar nicht vorkommen. Da dieser ganze Abschnitt aus der englischen Wikipedia übernommen wurde (vor einem Jahrzehnt), ist bestimmt niemand beleidigt, wenn er etwas umgekrempelt wird. @Burkhard, auch als "eher inaktiver" User bist du deutlich aktiver als ich – magst du dem Artikel helfen? --Zahnradzacken (Diskussion) 22:38, 7. Aug. 2015 (CEST)

Hm, bin definitv kein Experte für Automatentheorie - ich habe mich nur beim Basteln von digitalen Schaltungen mit dem Thema FSM beschäftigt. In diesem Bereich sind die Anwendungsmöglichkeiten zwar sehr konkret (z.B "rising edge detection") aber ich fürchte für OmA bereits zu abgehoben. Andererseits lassen sich dort die Gemeinsamkeiten und Unterschiede von Moore und Mealy recht kompakt und übersichtlich mit Zustandsdiagrammen und ASM-Charts gegenüberstellen, siehe z.B. [1].

Für den Normalleser scheint mir das Tür-Beispiel durchaus geeignet - wenn allerdings der Zwischenzustand beim Mealy-Automaten weggelassen wird, kann der Leser Moore und Mealy nicht mehr umittelbar vergleichen. Tatsächlich wird beim Türbeispiel eine Reduktion von vier (Moore) auf drei (Mealy) Zustände erreicht - das gibt die Abbildung so nicht wieder (der englische Artikel erwähnt dies ausdrücklich: The "opening" and "closing" intermediate states are not shown.). Mir scheint es daher nur logisch, die Abb. 4 entsprechend zu ergänzen. Der Motor bzw. die Türbewegung (öffend/schliessend) spielt in beiden Abb. die Rolle eines Vehikels, sollte aber IMHO erwähnt werden, da er für den/die Zwischenzustände und somit für das Verständnis wichtig ist - und zugleich den zeitlichen Aspekt berücksichtigt, dafür reicht - wie gesagt - auch die Bildunterschrift.

Übrigens: Einen ganz anderen Ansatz verfolgt der (ausgezeichnete) Artikel in der spanischen Wikipedia - dort wird das Thema in seiner ganzen theoretischen Pracht behandelt und ausschliesslich Mealy dargestellt, die Moore-Variante lediglich als mögliche Implementierung erwähnt.

Aber wie gesagt, ich würde eine Bearbeitung lieber den Kennern der Materie überlassen - mir fehlt dazu der Überblick. Beispiele und Abb.-vorlagen aus dem Bereich der Digitalelektronik könnte ich aber schon beisteuern. Gruß, --Burkhard (Diskussion) 12:14, 12. Aug. 2015 (CEST)

  1. ↑ Pong P. Chu: FPGA Prototyping by VHDL Examples, Wiley Interscience. 2008. S. 115-116
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Diskussion:Endlicher_Automat/Archiv&oldid=210851872“