DEAs minimalisieren

  • ist eigentlich ganz leicht:
    zuerts markierst du die endzustände da sich sich von denn anderen (nicht-end-) zuständen durch das leerwort unterscheiden.dann schaust du für die restlichen kantenpaare ob sie sich durch die eingabe eines zeichens
    unterscheiden;soll heissen das Du durch eingabe Von zb "2" von zustand a in einen schon markierten zustand kommst(beim ersten durchgang kann das nur ein Endzustand sein) und von zustand b aus in irgeneinen anderen (unmarkierten) Zustand.
    im prinzip wiederholst du diesen schritt einfaxch nur immer wieder bis du nur noch ununterscheidbare kantenpaare hast...
    wenn du willst kann ichs ja mal am beispiel im buch erklären...

  • fürchte ich habs noch immer nicht verstanden... bei mir kommt immer auch bei offensichtlich nicht minimalen automaten raus dass alle zustände unterscheidbar sind.


    also erklärs bitte noch an einem beispiel.

  • also mir machen diese blöden diagramme jetzt schon seit längerer zeit sehr zu schaffen ... habe sie jetzt nach dieser anleitung gemacht und denke auch, dass ich es im prinzip verstanden habe, nun aber meine frage:


    wann schreibt man 0, und wann 1? und warum gibt es fälle, bei denen man 11 eintragen muss ?????????????


    hab gedacht ich nehme bei der einen kante den wert 1, bei der anderen den wert 0, und je nachdem mit welcher kante man den endzustand erreicht, wird der jeweilige kantenwert im diagramm eingetragen.
    bin dankbar für jede hilfe

  • im diagramm wird immer das "wort" eingetragen, durch das sich die beiden zustände unterscheiden.


    angenommen man gelangt vom zustand A mit dem wort 01 in einen Endzustand, vom Zustand B allerdings nicht, dann sind die beiden zustände unterscheidbar und du trägst 01 in´s kästchen ein. natürlich können sich zwei zustände durch jedes beliebige wort (also auch 11 usw.) unterscheiden, kommt immer auf den automaten an.


    mfg, -z0nk-

    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  • Laut Skriptum hab ich das so verstanden:


    Wenn man sich das Beispiel 2.24 auf Seite 33 bzw. 34 anschaut dann muss man in dem Zustand "ag" 01 eintragen weil:
    Von "a" kommt man mit einer 0 nach "b". Also merkt man sich mal das "b". Von "g" bleibt man mit einer 0 in "g". Man erreicht also insgesamt den Zustand "bg".
    Nun schaut man, ob dieser Zustand schon in der Tabelle markiert ist. In diesem Fall stimmt es (mit 1 markiert). In der Tabelle wird nun das Übertragungssymbol mit dem man zum Zustand "bg" gekommen ist eingetragen ( 0 ) und der Zustand, der sich bereits in der Tabelle befand ( 1 ).
    So kommt man dann zu 01.
    10 würd in diesem Fall aber auch gehen, da man mit 1 zu "fe" kommt und das mit 0 bereits markiert ist.


    Analog geht man dann auch mit "ge" vor.

  • du suchst dir einen der ununterscheidbaren zustaende aus und ersetzt in der tabelle alle
    vorkommen der ununterscheidbaren zustaende durch diesen ausgewaehlten zustand.


    beispiel: sind {1}, {2} und {1,2} ununterscheidbar, suchst du dir z.b {1}
    aus und ersetzt alle vorkommen vor {2} und
    {1,2} durch {1}. die zeilen fuer {2} und
    {1,2} kannst du dann streichen, da diese
    zustaende nirgends mehr vorkommen.


    im graphen kann man sich das so vorstellen, dass man alle ununterscheidbaren knoten zu einem einzigen
    zusammenzieht und die kanten dabei mitnimmt.


    verstaendlich?


    nu

  • ich hab da so eine eigene methode,
    geht ein bisschen schneller:
    (script bsp 22.4)
    einfach eine tabelle machen:
    0 1
    a b f
    b g c
    .
    .
    also von wo aus man mit was hinkommt.
    dann hat man 2 gleiche zeilen -> das sind dann 2 nicht unterscheidbare zustände->einfach einen weglassen und in der tabelle noch den austauch berücksichtigen.


    cu m

  • Zitat

    Original geschrieben von MAZi
    ich hab da so eine eigene methode,
    geht ein bisschen schneller:


    dann hat man 2 gleiche zeilen -> das sind dann 2 nicht unterscheidbare zustände->einfach einen weglassen und in der tabelle noch den austauch berücksichtigen.


    damit erwischt du ein paar ununterscheidbare zustände aber nicht alle. z.b.:


    0 1
    a b c
    b c a
    c a b


    wenn a, b, c allesamt endzustände sind oder allesamt keine endzustände sind,
    dann sind diese drei zustände ununterscheidbar. erwischt du die mit deiner methode auch?


    nu

  • also der ausgangspunkt ist der DEA
    ^' 0 1
    A B A
    B C D
    C C E
    D B F
    E G F
    F G F
    G H E
    H H E


    wobei E,F,G,H endzustaende sind.


    in diesem fall gibt es mindestens zwei loesungswege:
    - die allgemeine methode mit der unterscheidbarkeitstabelle, die immer funktioniert
    - zweimaliges anwenden von MAZi's methode; die kann nie schaden, vereinfacht die situation, d.h., unterscheidbarkeitstabelle wird kleiner, erwischt aber unter umstaenden nicht alle ununterscheidbaren zustaende. in diesem fall tut sie es aber.


    also MAZi nr.1:
    E und F haben identische zeilen und sind beides die selbe art von zustand (end/nichtend); also alle F's durch E ersetzen.
    detto mit G und H: identische zeilen, beides endzustaende, also alle Hs durch G ersetzen.
    wir erhalten:
    A B A
    B C D
    C C E
    D B E
    E G E
    [F G E kann geloescht werden da keine F's mehr]
    G G E
    [H G E kann geloescht werden da keine H's mehr]


    MAZi nr.2:
    E und G haben identische Zeilen, sind beides endzustaende, also alle G durch E ersetzen.


    Voila! wie der franzose zu sagen pflegt.


    MAZi's methode versagt bei einem automaten wie
    0 1
    A B C
    B C A
    C A B
    (A,B,C endzustaende)


    unterscheidbarkeitsueberlegung:
    A und B unterscheiden sich durch ein wort das mit 0 beginnt, also durch 0w, falls sich B und C durch w unterschieden, da ich mit 0 von A nach B komme bzw von B nach C:
    (A,B) ---> (B,C) mit 0
    Analog mit 1:
    (A,B) ---> (C,A) mit 1


    da wir ueber (B,C) und (C,A) noch nichts wissen, bleibt der eintrag fuer (A,B) vorlaeufig noch leer, wir untersuchen die restlichen eintraege (A,C) und (B,C)
    (sind dasselbe wie (C,A) und (C,B)):
    (A,C) ---> (B,A) mit 0
    (A,C) ---> (C,B) mit 1
    (B,C) ---> (C,A) mit 0
    (B,C) ---> (A,B) mit 1


    damit haben wir alle paare untersucht, bei keinem konnten wir unterscheidbarkeit feststellen, sondern nur verweise auf andere ununterscheidbare zustaende.
    also koennen A,B,C zusammengefasst werden.


    so einfach ist das :-)


    nu

  • ok.....erwischt und sehr hübsch bewiesen. meine methode versagt bei solchen "cyklischen" automaten wo ein zeichen immer auf den nächstliegenden knoten verweist (bzw. wenn vom größten weg, auf den anfangs-knoten) und ein anderes zeichen in die genrichtung zeigt.
    allerdings erkennt man solche konstruktionen spätestens dann wenn man den DEA aufzeichnet wobei ein vorkommen einer solchen struktur überhaupt höchst selten ist dadurch, daß man ja zuerst beginnt einen NEA zu zeichnen und man so eher nicht auf so eine strukt. stößt. denn (um beim bsp. zu bleiben) dieser automat ist nix anderes als [0,1]* was man ja vieeel leichter darstellen kann! (und vermutlich auch wird wenn man das tolle TI script gelesen hat und/oder in der VU war) . cu MAZi
    ps. am 28.11 is es soweit!