DEA oder NEA (Automat)?
Ich wollte mal eure meine dazu wissen, ob dieser endliche Automat deterministisch ist oder nichtdeterministisch ist?
Meiner Meinung nach ist dieser Automat nichtdeterministisch, weil es kein eindeutigen Startzustand gibt, da man mit b oder c das Wort anfangen kann.
Lg
2 Antworten
Er ist deterministisch.
Der Pfeil links neben s0 kennzeichnet s0 als (einzigen) Startzustand. Dass oder ob man verschiedene Wörter erzeugen kann, hat mit Determinismus und Nicht-Determinismus nichts zu tun. Determinismus schlägt dann fehl, wenn es in einem Zustand für ein Zeichen mehrere mögliche Übergänge gibt (oder gar keinen).
Ausschlaggebend hier ist, dass es in jedem Zustand jeweils genau einen Übergang für a, b und c gibt (d.h. es fehlt nirgends ein Übergang für ein Zeichen und es gibt nirgends mehrere Übergänge für dasselbe Zeichen). Das zeichnet den Automaten als DEA aus.
Ich hätte da noch eine Frage... Wenn ich die Menge der Wörter die von s0 nach s1 überführen ohne den Zustand s0 ein zweites mal zu besuchen in einem regulären Ausdruck abgeben soll könnte es so aussehen ?
{b,c}^* a ?
Das kommt darauf an, ob "kein zweites Mal besuchen" auch bedeutet, dass ein Zustandsübergang von s0 nach s0 verboten ist. Wenn ja, muss es ja am Anfang gleich mit einem a zu s1 weitergehen, denn b, c würden wieder in s0 führen. Anschließend kann es nur beliebig viele weitere a geben, denn b oder c würden in s3 führen und von dort gibt es keinen Übergang mehr zu s1.
Heißt: Erst genau ein a (damit kommt man von s0 nach s1) und dann beliebig viele weitere a (womit man immer in s1 verbleibt). Als regulärer Ausdruck: a(a)*.
Ist der Zustandsübergang von s0 nach s0 erlaubt, können am Anfang noch beliebig viele b oder c dazukommen, d.h. (b|c)*a(a)*. (Oder eben mit geschweiften Klammern, je nachdem was für eine Notation du verwendest.)
Das ist aber nicht das Unterscheidungskriterium für deterministische und nichtdeterministische Automaten. Das Kriterium für die Unterscheidung ist, ob der Automat bei gleicher Eingabe das gleiche Ergebnis liefert. Bei einem nichtdeterministischen Automat gibt es quasi ein "Zufallselement", welches eben dafür sorgt, dass der Automat bei gleicher Eingabe unterschiedliche Ergebnisse liefert.
Trifft hier ein oder, da man nicht weiß ob b oder c am anfang
Nein. Es ist ganz egal, mit was Deine Eingabe anfängt. Sie darf halt mit b oder c anfangen. Entscheidend ist, ob der Automat dasselbe tut, wenn Du dieselbe Eingabe reingibst.
Ok danke!