sichere methode zum zeichnen von dea 's

[paco89]

hi,

kann mir jmd. sagen, ob es eine sichere methode zur konstruktion von DEA' s existiert?
wenn bspw. die sprache, die akzeptiert wird, gegeben ist und man soll dazu ein DEA konstruieren, wie geht man da vor....?
immer wenn ich meine skizzen mit den lösungen der tutoraufgaben vergleiche, habe ich ein paar fehler....
ich habe das mal mit einer übergangstabelle versucht, aber die macht doch nur dann sinn, wenn man den übergangsgraphen hat, und nur ablesen muss, oder?

ich würde gerne wissen, ob es eine sichere methode gibt, oder ob man einfach nur lange üben muss, bis die erfahrung so groß ist, dass man jede akzeptierte sprache aus dem bauch heraus mit einem übergangsgraphen darstellen kann....

[ZaKaRy]

wenn ich mich richtig erinner kann man für eine gegebene Sprache relativ easy einen nichtdeterministischen endlichen Automaten konstruieren, aus dem macht man mit einer Potenmengenkonstruktion (http://de.wikipedia.org/wiki/Potenzmengenkonstruktion) dann einen DEA. Genau weiss ich es leider nicht mehr, ist ein paar Semester her ...

[Vion]

Die Frage ist was du für Fehler machst.
Wenn du Kanten vergisst und der Automat damit nicht deterministisch ist, kann man das natürlich vermeiden.
Ansonsten kenn ich keinen Lösungsweg der dich immer zum richtigen Automaten führt.
Da hilft einfach nur üben.

Die NFA Methode ist zwar nicht schlecht, kann den Automaten aber schnell groß werden lassen.

[fw]

Das kommt wohl immer drauf an auf welche Art und Weise die Sprache beschrieben ist. Aus regulären Ausdrücken kann man recht einfach (algorithmisch, ohne nachdenken) einen NEA machen. Diesen kann man deterministisch machen und anschließend minimieren. Sowas per Hand zu machen ist aber meistens sehr langsam, "scharf hinsehen" ist oft schneller

[paco89]

ja, danke ersteinmal für die antworten. ich meinte eigtl. die typischen aufgaben, wo bspw. steht :
L= {w aus Sigma* mit der Eigenschaft, dass w ein Infix ab enthält}

und solche ähnlichen aufgaben halt. ihr wisst, was ich meine, ne? also die sprache ist gegeben und man soll daraus einen DEA oder NEA basteln. irgendwie baue ich mir immer wieder fehler ein, obwohl ich mir richtig viele gedanken vor dem zeichnen mache. entweder fehlt mir eine transition oder ich habe einen zustand vergessen. ich find das echt paradox, dass ich die komplizierteren sachen verstehe, aber wenn es ums einfache zeichnen von DEA's oder NEA's geht, ist die fehlerquote sehr hoch.
und da jetzt die klausur nächste woche ist, macht mich da schon verrückt, falls solche aufgaben drin vorkommen sollten und ich diese geschenkten punkte liegen lasse. bekommt man in solchen fällen auch punkte für den ansatz oder werden einem bei der präsenübung bei solchen sachen einfach null punkte gegeben, weiß das jḿd. vtl? ich mein ich werd das noch unzählige mal üben, aber wenn man punkte für den ansatz bekommt, würd mich das schon sehr beruhigen....

[Vion]

Meistens ist es so, dass man auch Teilpunkte bekommt sofern zu erkennen ist, dass man sich die richtigen Gedanken gemacht hat.
Wenn aber ein DFA verlangt ist und man nen reinen NFA malt wird man wahrscheinlich 0 Punkte bekommen.

Aber wenn dir bei nem DFA z.B. Transitionen fehlen dann solltest du dir nochmal die Definition eines DFAs angucken Das sind Fehler die wirklich vermeidbar sind

[Gibtnix]

Ich hatte damals in FoSAP die gleichen Probleme... eigentlich ist das Prinzip total simpel aber sobald der reguläre Ausdruck etwas größer / komplizierter wird, baut man ganz schnell eine Transition in einen falschen Zustand ein / vergisst irgendwas / etc.

Jedenfalls wenn ich mich an FoSAP richtig erinnere gab es sowas wie einen Kreuzautomaten oder sowas (meine NICHT den Potenzautomaten), damit bastelt man aus einem Automat, der L1 erkennt, und einem weitern, der L2 erkennt, einen Automaten, der dann L1 L2 oder L1 + L2 erkennt. Weiß nicht mehr wie das genau war, aber das hat mir damals etwas weiter geholfen.

Ansonsten gibt es schon eine Möglichkeit das grundsätzlich zu lösen (Lernalgorithmus). Aber das macht man eigentlich erst in weiterführenden Vorlesungen und ist für die einfacheren Aufgaben in FoSAP wahrscheinlich etwas overkill. Aber funktionieren tut der auf jeden Fall und ich war beeindruckt von diesem, als ich ihn das erste mal selbst durchgerechnet habe.

[paco89]

schade, dass es keine sichere methode gibt, wie man das anpacken kann....dann muss ich wohl üben, üben und weiter üben bis ich das dann auch ausm ärmel schütten kann.

[NeX]

L= {w aus Sigma* mit der Eigenschaft, dass w ein Infix ab enthält}

Für so eine Sprache würde ich gar keinen regulären Ausdruck basteln nur um ihn dann umzuwandeln.

Auch hier gilt: Gucke dir Sprache an und mache Beispiele, danach bastel einen Automaten und vergleiche...

Anforderungen: Infix ab

Und dir sollte folgendes bewusst sein

• Am Anfang: darf alles vorkommen
• Es muss mindestens einmal ab vorkommen
• Am Ende: darf alles vorkommen

Nun weisst du doch bereits, dass du mit 3 Zuständen (1,2,3)
sicherstellen kannst, dass ab vorkommt

Von 1 nach 2 mit a
Von 2 nach 3 mit b

Nun musst du dir überlegen was sonst noch vorkommen kann,
und wie du es realisieren kannst.