Fachrat Informatik - Forum

Hm, deterministisch oder nicht. Also ich krieg da nur deterministische Automaten raus. Is aber wohl egal, da deterministische auch zu den nichtdeterministischen gehören....

wenn dein automat z.B. aus dem zustand S0 mit einem 'a' in den zustand S1 gehen kann u n d mit einem 'a' von S0 auch in S2 gehen kann, oder es epsilon übergänge gibt, dann ist das teil nichtdeterministisch.
wenn es für jedes eingabezeichen aus jedem zustand nur einen übergang gibt, ist er deterministisch.
ist glaubich das gleiche, das migu auch gesagt hat nur ich kanns mir so leichter vorstellen....

dann könnte man den ganzen automaten ja so aufbauen, dass er den ersten buchstaben liest und sobald er beim nach rechts laufen auf den gleichen trifft, die beiden "ausgleicht"...

dann wär er aber so heftig nicht deterministisch, dass man erst am ende erkennen würde, welche übergänge benutzt wurden ...kann nich sein....

aber ansonsten...naja...weiss keine anwendung so direkt, mal sehn was in der übung gesagt wird

schauschau

Wolfram

Hm, funktion relation... auf jeden Fall is meiner deterministisch und das darf er laut Übung wohl auch sein, auch wenn da nichtdeterministisch steht, allerdings soll nichtdeterministisch einfach er sein. Ich persönlich finds aber schwieriger vorzustellen und zu konstruieren. naja, abwarten..

find ich eher, dasser mellow laid back (usw.) guckt...so leichte linksneigung, hab auch das ganze bild...



was ne bande von verrückten...

Tach alle zusammen!

Weiß nicht, ob's jetzt noch jemandem nützt, aber so erkläre ich mir immer die Funktionsweise eines nichtdeterministisch arbeitenden Automaten:

Ein deterministischer Automat wechselt in einen anderen Zustand, wenn die gegebene Situation die Voraussetzungen dafür erfüllt. Es gibt dabei immer nur einen möglichen Folgezustand. Der Automat arbeitet sozusagen linear, das heißt, entweder geht's weiter, oder halt nicht.

Bei einem nichtdeterministischer Automaten hingegen gibt es mehrere mögliche Folgezustände: Die Voraussetzungen für den Wechsel in diese Folgezustände sind gleich, nur in ihren Auswirkungen unterscheiden sie sich. Was macht der Automat in diesem Fall? Er kann sich ja nicht einfach (in weiser Voraussicht) für eine der mehreren möglichen Reaktionen entscheiden!

Also verfolgt er einfach alle Möglichkeiten parallel, er verzweigt sozusagen in seinem Ablauf und es bildet sich ein Ablauf-Baum. Die Blätter (ganz außen) repräsentieren dann jedes mögliche Programmergebnis und wenn darunter ein Gültiges ist, hat die Eingabe die Bedingungen, auf die sie mittels des Automaten getestet wurde, erfüllt.

Auf die Art und Weise braucht zum Beispiel ein Automat, der herausfinden soll, ob ein Wort von der Art ww^r ist, nicht zu wissen, wo die Mitte des Wortes ist. Bei jedem weiteren gelesenen Symbol des Eingabewortes verzweigt er einfach in zwei Zweige: Ein Zweig geht davon aus, er hätte die Mitte gefunden, der andere geht davon aus, daß er die Mitte des Wortes noch nicht erreicht hat. Wenn das Wort tatsächlich von der Art ww^r war, wird sich unter all den verschiedenen Ergebnissen ein Gültiges befinden und der Automat hat das Wort erkannt. Befindet sich jedoch kein gültiges Ergebnis in den Blättern des Baumes, war das Wort nicht von der Art ww^r.

Wer das verdaut hat, verdient Respekt , kürzer ging's irgendwie nicht.

Bassim

@migu

ist ja witzig, dein zweimarkstück dreht sich jeden tag um pi/4 weiter. kann also keine kapazität sein...

ok, war flach. zum nichtdeterminismus: stell dir eine zu akzeptierende sprache vw mit w gleich v rückwärts, also zum Beispiel abccba.

deterministische lösung ist klar. erstes zeichen lesen + markieren, letztes zeichen dagegen abgleichen usw... kein problem.

nichtdeterministische lösung: einen zustand s0, der jedes zeichen lesen kann und immer einen nach rechts geht, bis er am # ankommt und gleichzeitig ein beliebiges zeichen lesen und markieren kann und in einen anderen zustand wechselt, der dann aus der mitte heraus buchstaben abgleicht.
für s0 sieht das ungefähr so aus: delta = {(s0,a,s0,a,r),(s0,b,s0,b,r)......(s0,a,s1,A,r),(s0,b,s1,B,r)......}

nichtdeterministisch bedeutet einfach nur, dass man für ein und dieselbe konfiguration verschiedene folgekonfigurationen baut und damit ist es möglich, wie oben die mitte eines wortes zu "raten". bestimmte "falsche" benutzung von übergängen (nicht in der mitte des wortes) sind also erstmal möglich, führen aber letztendlich zu keinem ziel.

hoffe, es ist klarer geworden, wie man sowas programmiert.

eike