DEAs minimalisieren
Results 1 to 14 of 14
  1. #1

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts

    DEAs minimalisieren

    könnte mir irgendwer erklären wie diese unterscheidbarkeitstabelle zum minimalisieren von automaten funktioniert?

    ich versteh die erklärung im skriptum irgendwie nicht...

  2. #2
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...
    ALL GLORY TO THE HYPNO TOAD...

  3. #3

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  4. #4
    Eulalia's Avatar
    Title
    Elite
    Join Date
    May 2002
    Posts
    302
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  5. #5
    -z0nk-'s Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    169
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  6. #6
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    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.
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

  7. #7
    nexus's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Location
    Wien
    Posts
    272
    Thanks
    7
    Thanked 0 Times in 0 Posts
    wie kann man die ununterscheidbare zustände zusammenfassen?
    kann mir dass jemand erklaeren?
    "Socialism is Bolshevism with a shave."
    -'Detroit Journal'

  8. #8
    Neutrino's Avatar
    Title
    Hero
    Join Date
    Apr 2002
    Posts
    237
    Thanks
    0
    Thanked 7 Times in 1 Post
    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

  9. #9

    Title
    Principal
    Join Date
    Jun 2002
    Posts
    32
    Thanks
    0
    Thanked 0 Times in 0 Posts

    minimieren

    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

  10. #10
    Neutrino's Avatar
    Title
    Hero
    Join Date
    Apr 2002
    Posts
    237
    Thanks
    0
    Thanked 7 Times in 1 Post

    Re: minimieren

    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

  11. #11
    nexus's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Location
    Wien
    Posts
    272
    Thanks
    7
    Thanked 0 Times in 0 Posts
    :eek:
    Ich verstehe es nicht so ganz, koenntest du es anhand Aufgabe 1.7 zeigen? hier den Linkhttp://www.logic.at/lvas/thinf1/beispiele/blatt-01.pdf

  12. #12
    nexus's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Location
    Wien
    Posts
    272
    Thanks
    7
    Thanked 0 Times in 0 Posts
    Da ist naehmlich:
    ^' 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
    dann kommt man auf:

    ^'' 0 1
    A B A
    B C D
    C C E
    D B E
    E E E

    ????

  13. #13
    Neutrino's Avatar
    Title
    Hero
    Join Date
    Apr 2002
    Posts
    237
    Thanks
    0
    Thanked 7 Times in 1 Post
    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

  14. #14

    Title
    Principal
    Join Date
    Jun 2002
    Posts
    32
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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!

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •