Automat zu Bsp. 1 des letzten Tests
Results 1 to 32 of 32
  1. #1
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Question Automat zu Bsp. 1 des letzten Tests

    Gegeben ist der egrep-Ausdruck:
    (BC?)*[AC]?[BA]+
    Man soll nun den minimalen det. Automaten angeben. (=gleiche Bsp. wie das 1. von Gruppe A)

    Ich bin auf folgenden indeterministischen Automaten gekommen, der im Anhang beigefügt ist. Da ich bei der erweiterten Übergangsfunktion auf 16 Zustände gekommen bin, ist meine Frage, ob der Automat überhaupt so richtig sein kann?

    Bin mir vor allem beim 1. Ausdruck (BC?)* nicht im Klaren, wie ich den darstellen soll.
    "*" heißt ja, dass der Ausdruck öfters vorkommen kann - deshalb eine Schleife. Mit "C?" kann das Zeichen maximal 1x vorkommen. Da aber jetzt wiederrum das "B" beliebig oft vorkommen kann, hab ich im 2. Zustand eine "B-Kante" auf sich selbst gerichtet. Dadurch sollten ja Ausdrücke wie: "bcbbb", "bbbbc" oder "bbcbb" usw. möglich sein, was dem 1. Ausdruck entspricht.

    Frage: Ist jetzt der Automat so "schlau" und merkt sich, dass er die "C-Kante" nur 1x benutzen darf?

    Sollte jemand eine richtige oder bessere Lösungen haben - bitte, bitte hier posten! Brauch beim Test im Herbst jeden Punkt!
    DANKE!
    Attached Images Attached Images  
    Last edited by patricasso; 11-09-2002 at 20:21.
    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-----------

  2. #2

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    kleine Anmerkung mal:
    ich glaube, am ende bei [BA]+ funktioniert dein automat nicht. du akzeptierst, sobald du in zustand 5 oder 6 bist nämlich entweder nurmehr As oder nurmehr Bs..
    es könnte aber am Ende noch ABABABABABA.... weitergehen.

    das (BC?)* schaut gut aus, find ich
    /edit: Habs nochmal nachgeprüft und es stimmt definitiv


    mfg, Chris
    Last edited by Chris; 11-09-2002 at 21:34.
    hi, i'm a signature virus. copy me into your signature to help me spread.

  3. #3
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    Aha!
    Ja stimmt - die beiden Kanten bei den Zuständen 5 und 6 gehören irgendwie geändert. Muss mir das aber erst mal genauer anschauen - heute is mir schon zu spät.

    Mit einer "AB-Kante" würds ja auch nicht gehen, oder? Dann kann ja das "A" oder "B" wieder beliebig oft hintereinander vorkommen, höchstens der Automat wechselt immer hin-und her (einmal A dann B, dann A ... usw.).

    Vielen Dank auf jeden Fall für die rasche Hilfe!
    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-----------

  4. #4

    Title
    Hero
    Join Date
    Mar 2002
    Posts
    228
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hab leider no nix gelernt, muss ich mir erst mal anschauen.
    dafür bekommst die

    Prüfungstermine
    Für beide Termine ist eine Anmeldung bis 24 Stunden vor dem jeweilen Termin über diese Seite notwendig. Bis zum 24.10. ist keine Doppelanmeldung möglich, d.h., Sie müssen sich vorerst für einen der beiden Termine entscheiden.

    Do, 24. Oktober 2002, 16:30-18:30, AudiMax
    Do, 28. November 2002, 16:30-18:30, AudiMax

  5. #5
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hier mal mein versuch:
    theo1 sind die deterministischen automaten für die teilprobleme.
    dann hab ich die teile mit Epsilon kanten verbunden
    (Ap.1 mit Ap.2 & Ap3.;und Ap.2 mit Ap.3)
    als nächstes hab ich das ganze "determinisiert"
    siehe theo2
    alle zustände sind endzustände.kann jemand sagen ob das stimmt?

    PS:weiss jemand ein programm um solche skizzen zu erstellen?mit paint wird das ein bisschen unübersichtlich
    Attached Images Attached Images  
    ALL GLORY TO THE HYPNO TOAD...

  6. #6
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    blöd das man ned mehrere files anhängen kann..
    Attached Images Attached Images  
    ALL GLORY TO THE HYPNO TOAD...

  7. #7
    Wings-of-Glory's Avatar
    Title
    CO-Administrator
    Join Date
    Jan 2002
    Posts
    4,001
    Thanks
    347
    Thanked 504 Times in 266 Posts
    Original geschrieben von Shade
    blöd das man ned mehrere files anhängen kann..
    Ja, hast recht. Mit einem Zip-Programm (zB Winace) kannst du das Problem umgehn.
    Otto: Apes don't read philosophy. - Wanda: Yes they do, Otto, they just don't understand
    Beleidigungen sind Argumente jener, die über keine Argumente verfügen.
    «Signanz braucht keine Worte.» | «Signanz gibts nur im Traum.»


    Das neue MTB-Projekt (PO, Wiki, Mitschriften, Ausarbeitungen, Folien, ...) ist online
    http://mtb-projekt.at

  8. #8

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @shade:
    mit visio geht das sicherlich ganz nett zu zeichnen... (halt nur unter windows)

    deine (BC?)* und [AC]? automaten sind ok, beim letzten könnte man die zustände 2 und 3 zwecks minimierung zusammenfassen, glaub ich.

    insgesamt sind sicherlich nicht alle zustände endzustände, weil zum ende ja ein A oder B kommen muss (dass [AB]+ kann man nicht so einfach wie einen * oder ein ? "überspringen")

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  9. #9
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    danke,habs nochmal überarbeitet.hier die richtige version...bei der alten waren leider ziemlich viel fehler drinnen...
    Attached Files Attached Files
    ALL GLORY TO THE HYPNO TOAD...

  10. #10

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hmm... bei deinem (BC?)* Automaten hast du da eine Epsilonkante zuviel, würde ich mal sagen, nämlich die von q0 nach q1, die sollte wohl eher von q0 nach q2 gehen, und das schlägt sich dann eben auch im determinisierten Automaten nieder.

    Außerdem könntest du, wie schon gesagt, q5 und q6 zusammenlegen, da die beiden ununterscheidbar sind...

    ansonsten passts

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  11. #11
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja,ich befürchte du hast recht.aber dieses q5&q6 sieht ein bisschen komisch aus...2 doppelt beschriftete kanten naja vielleicht stelle ich mal ne richtige voll minimierte version ins netz.aber auf alle fälle danke für die hilfe
    ALL GLORY TO THE HYPNO TOAD...

  12. #12
    Jimmy's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    539
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Kann mir jemand vielleicht den Egrep Ausdruck (BC?)*[AC]?[BA]+ in einer regulaeren Menge uebersetzen? also mit Verkettung,Vereinigung und Stern, ...
    danke.

  13. #13

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ({B} · ({C} ∪ {ε}))* · ({A} ∪ {C} ∪ {&epsilon}) · {B} · {A} · ({B} &middot {A})*

    hmm.. kanns das sein?

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  14. #14

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    denke eher das ist ({B} · ({C} ∪ {ε}))* · ({A} ∪ {C} ∪ {ε}) · ({B} ∪ {A})+ .

    [xy] bedeutet doch {x} ∪ {y} oder? und + gibts ja bei mengen auch, das muss man nicht so umständlich schreiben.

  15. #15

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja, hast recht, beim punkt hab ich mich verschrieben. die andere eckige klammer stimmt eh bei mir auch

    wegen dem + : bei der formalen definition regulärer mengen ist das plus eben nicht dabei. (natürlich sind sie aber unter dem + - operator abgeschlossen.)

    mfg, Chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  16. #16
    Jimmy's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    539
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Kurze Frage noch: wie seids ihr genau bei der Konstruktion von Automaten vorgegangen? also, wenn ich da sowas zambau dann krieg ich ein Megakomplex mit mehr als xx Zustaende, also ich geh so wie der Salzer es im Skriptum schreibt vor:

    - Egrep in regulaerer Menge umwandeln
    - den reg.Ausdruck mit Hilfe der Verkettungs-,Vereinigungsgrafiken auf Skriptumseite 28 in einen NEA umwandeln,
    gut jetzt schaut das Ding schon uur gross aus, eure NEAs oben sind aber ziemlich klein-wieso das?
    -NEA in DEA umwandeln und dann minimieren...

    was mach ich bloss falsch?
    Der beste Beweis, dass ausserirdische Intelligenz existiert, ist der dass bis jetzt noch keiner Kontakt zu uns aufgenommen hat

  17. #17
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    naja ,ich hab die einzelnen Egrep ausdrücke als NEA konstruiert,dann sinngemäßmit epsilonkanten verbunden
    (i.e wenn der zweite automat optinal ist,mach ich auch ne epsilon kante vom ersten zum dritten) und dann minimalisiert/determinisiert...
    ALL GLORY TO THE HYPNO TOAD...

  18. #18
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Lukas
    denke eher das ist ({B} · ({C} ∪ {ε}))* · ({A} ∪ {C} ∪ {ε}) · ({B} ∪ {A})+ .

    [xy] bedeutet doch {x} ∪ {y} oder? und + gibts ja bei mengen auch, das muss man nicht so umständlich schreiben.
    hallo!
    gibt es für diese übersetznung eine tabelle im skript und wenn ja bitte wo, ich komm grad überhaupt nicht weiter!
    danke!
    never underestimate the power of denial

  19. #19
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Lukas
    denke eher das ist ({B} · ({C} ∪ {ε}))* · ({A} ∪ {C} ∪ {ε}) · ({B} ∪ {A})+ .

    [xy] bedeutet doch {x} ∪ {y} oder? und + gibts ja bei mengen auch, das muss man nicht so umständlich schreiben.
    hallo!
    gibt es für diese übersetznung eine tabelle im skript und wenn ja bitte wo, ich komm grad überhaupt nicht weiter!
    danke!
    never underestimate the power of denial

  20. #20
    Jimmy's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    539
    Thanks
    0
    Thanked 0 Times in 0 Posts
    auf Seite 21 im Juni'02 Skriptum findest du so eine Tabelle, ist aber nur auf deutsch erklaert, als reg.Menge muss man sich das selber zamreimen
    Der beste Beweis, dass ausserirdische Intelligenz existiert, ist der dass bis jetzt noch keiner Kontakt zu uns aufgenommen hat

  21. #21
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts
    danke für deine antwort, aber das ganze sagt mir irgendwie nicht viel. könnte das irgendwer genauer erklären, wie man darauf kommt, was für ein ? steht und wie man die egrep ausdrucke umformt?
    ewiger dank!
    never underestimate the power of denial

  22. #22
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    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).
    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-----------

  23. #23
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts
    könntest du kurz erklären wie du die egrep ausdrücke gleich umwandelst, danke
    never underestimate the power of denial

  24. #24
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    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.
    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-----------

  25. #25
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts

    richtig?

    könnt sich bitte wer meinen automaten dazu ansehen und sagen was er davon hält?
    danke!!
    Attached Images Attached Images  
    never underestimate the power of denial

  26. #26
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    #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.
    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-----------

  27. #27
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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!
    ja, das eps ist ein schreibfehler!
    never underestimate the power of denial

  28. #28

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Attached Images Attached Images  
    Last edited by Chris; 21-10-2002 at 00:11.
    hi, i'm a signature virus. copy me into your signature to help me spread.

  29. #29
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich weiss nicht, ich bekomm 6 zustände zum schluss, der ganze automat schaut aber verwirrend aus. ich geh morgen zum salzer in die sprechstunde und frag ihn, schicke dann die antwort!
    never underestimate the power of denial

  30. #30

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    hi, i'm a signature virus. copy me into your signature to help me spread.

  31. #31
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ich komm zuerst auf 7 zustände und beim minimieren fällt 1 weg, bleiben 6!!
    never underestimate the power of denial

  32. #32
    enola's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    139
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hallo! tut mir leid, dass ich jetzt erst antworte. dein automat ist glaub ich richtig, aber inzwischen gibt es die lösungen vom letzten test eh online!
    never underestimate the power of denial

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
  •