View Full Version : [Frage] Automat zu Bsp. 1 des letzten Tests
patricasso
11-09-2002, 20:16
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!
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
patricasso
11-09-2002, 21:18
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!
Compiler
13-09-2002, 11:19
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
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;)
blöd das man ned mehrere files anhängen kann..
Wings-of-Glory
13-09-2002, 21:42
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. :)
@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
danke,habs nochmal überarbeitet.hier die richtige version...bei der alten waren leider ziemlich viel fehler drinnen...
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
ja,ich befürchte du hast recht.aber dieses q5&q6 sieht ein bisschen komisch aus...2 doppelt beschriftete kanten:eek2: naja vielleicht stelle ich mal ne richtige voll minimierte version ins netz.aber auf alle fälle danke für die hilfe :)
Kann mir jemand vielleicht den Egrep Ausdruck (BC?)*[AC]?[BA]+ in einer regulaeren Menge uebersetzen? also mit Verkettung,Vereinigung und Stern, ...
danke.
({B} · ({C} ∪ {ε}))* · ({A} ∪ {C} ∪ {&epsilon}) · {B} · {A} · ({B} · {A})*
hmm.. kanns das sein?
mfg, Chris
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.
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
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? :confused:
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...
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!:hewa:
danke!
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!:hewa:
danke!
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
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!
patricasso
19-10-2002, 02:02
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).
könntest du kurz erklären wie du die egrep ausdrücke gleich umwandelst, danke
patricasso
19-10-2002, 17:08
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.
könnt sich bitte wer meinen automaten dazu ansehen und sagen was er davon hält?
danke!!
patricasso
20-10-2002, 18:33
#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.
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
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!
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
ich komm zuerst auf 7 zustände und beim minimieren fällt 1 weg, bleiben 6!!
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!
vBulletin® v3.7.1, Copyright ©2000-2008, Jelsoft Enterprises Ltd.