Automat zu Bsp. 1 des letzten Tests

  • ich hab die egrep Ausdrücke gleich direkt umgewandelt - also ohne das Zeugs mit ({B} · ({C} ∪ {ε}))*usw. ...
    Es wird ja nicht verlangt, dass man das auch macht, oder?


    Hab aber übrigens das gleiche Problem wie Jimmy (# 16). Bei mir kommen auch zig Zustände raus, obwohl die Automaten stimmen müssten.
    Könnte vielleicht jemand eine Lösung vom letzten Test (Bsp. 1 Gr. A) hier posten? Vielleicht komm ich ja dann endlich dahinter, was falsch sein könnte.


    zu #21 (kurz):
    "?" steht für ein oder kein mal => beim Automaten kanns sicher keine Schleife geben bzw. keine "zurück" Kante (im Gegensatz zum "*" Ausdruck).

  • zu #23 - einfaches Beispiel:


    Ich hab im 1. Post in diesem Thread veruscht den Egrep-Ausdruck vom letzten Test umzuwandeln. Meine Lösung dazu kann man sich auch dort downloaden (indet-automat.jpg).


    Wenn du dir den ersten Ausdruck anschaust lautet der:
    (BC?)*


    Da der gesamte Ausdruck mit einem "*" Operator endet, kann der komplette Ausdruck (BC?) entweder 0x oder undendlich viel mal vorkommen.
    Mit der epsiolon-Kante von Zustand (1) weg, kann also der Ausdruck auch nie auftreten und gleich zum Zustand (3) gehen.


    Falls jetzt ein "a" kommen sollte springt der Automat von (1) auf (2). Von dort aus kann er entweder mit "a" im Zustand (2) bleiben, oder aus dem gesamten Ausdruck mit der epsilon-Kante rausspringen, oder mit "b" wieder zurück zu (1) gelangen.
    Warum? Weil das "?" einfach 1x oder niemals bedeutet. Das heißt, dass das "b" höchstens 1x im Ausdruck vorkommen kann. Da aber das "a" keinen zusätzlichen Operator hat, kann es beliebig oft vorkommen ( daher die Schleife im (2) ).
    Somit sind folgende Zustände möglich:
    aaaaaa -> (3)
    abaa -> (3)
    {} -> (3)
    a -> (3)
    aaaaab -> (3)
    aabaaa -> (3)
    ...


    Ich hab das jetzt einfach für jeden x-beliebigen Ausdruck so angewendet und komm so relativ schnell zu einem Automaten. Für Ausdrücke wie (a*b?c+)* brauch ich somit nicht mal mehr eine Minute fürn Automaten.


    Hoffe ich konnte die Frage einigermaßen gut beantworten.

  • #25:
    Würd das epsiolon zwischen den mittleren und den Endzustand weglassen, da der Ausdruck [BA]+ mindestens 1x vorkommen muss. Bei "+" Ausdrücken hab ich nie eine epsilon-Kante verwendet. Ansonsten könnts aber stimmen.

  • Zitat

    Original geschrieben von patricasso
    #25:
    Würd das epsiolon zwischen den mittleren und den Endzustand weglassen, da der Ausdruck [BA]+ mindestens 1x vorkommen muss. Bei "+" Ausdrücken hab ich nie eine epsilon-Kante verwendet. Ansonsten könnts aber stimmen.


    danke! :thumb:
    ja, das eps ist ein schreibfehler!

  • hmm.. bin ich jetzt komplett blind, oder hat hier wirklich noch niemand einen minimalen det. autmaten für das 1. beispiel gepostet?
    naja, hier ist auf jeden fall meine lösung, was haltets ihr davon?


    (kommt mir ein bisserl klein vor, aber hab keinen fehler gefunden)


    /edit: Da kommt natürlich noch eine Kante dazu, die vom Knoten 4 zum selben Knoten geht und mit 'B' beschriftet ist..


    mfg, Chris

  • ja, ich komm auch auf 6 zustände, beim minimieren fallen mir dann aber 2 weg..


    bitte, poste dann die antwort vom salzer hier, würde mich interssieren, ob das jetzt auch wirklich stimmt...


    mfg, Chris