 Automaten/reg. Ausd. und R(i,j,k) |
Traidos
Grünschnabel
Dabei seit: 01.11.2009
Beiträge: 4
 |
|
|
01.11.2009 15:01 |
|
|
|
|
Es gibt einen Tabellen-Algorithmus, mit dem man den Automaten immer weiter in seine Einzelbestandteile zerlegt und damit dann den regülären Ausdruck bestimmen kann.
Das ganze ist aber sehr sehr aufwendig, weshalb man das ganze meist durch "geschicktes Hinsehen" löst.
Meistens sind die Automaten ja nicht recht kompliziert, weshalb das Try-And-Error-Verfahren recht oft klappt.
Ich weiß jetzt leider nicht genau, wo ich meine alten Unterlagen habe. Aber der Prof meinte damals, dass der Algo für Klausuren nicht prakabel ist.
Was du mit 2. meinst weiß ich grad leider nicht.
Was ist diese R-Funktion?
|
|
|
01.11.2009 21:27 |
|
|
Traidos
Grünschnabel
Dabei seit: 01.11.2009
Beiträge: 4
|
|
Das ist eigentlich genau diese tabellarische Form, wie ich gerade herausgefunden habe, wozu ich gleich mal ne Frage habe.
Ich versuch hier mal ein Bsp. zu geben.
Wenn ich einen Automaten habe mit 4 Zuständen. 4 und 3 sind akzeptierend, 1 ist der Startzustand und dann sieht das so aus:
1->c->2
1->a->4
2->a->2
2->a->1
2->c->3
3->a,c->3
4->a->1
Das sind meine Übergänge ( von Zustand 1 mit Eingabe c zum Zustand 2 ... )
Dann bastel ich mir ja die Tabelle, die für die Ersten so aussehen müsste:
R(1,1,1)=Leere Menge+(LM)(LM)*(LM)
R(1,2,1)=c+(LM)(LM)*(LM)
R(1,3,1)=(c+c)+(LM)(LM)*(c+c)
... Und immer so weiter
Um das zu bauen nutze ich ja dann diese Formel:
R(i,j,1)=R(i,j,0)+R(i,1,0)R(1,1,0)*R(1,j,0)
So, meine Frage ist nun, muss ich in die Tabelle auf die Übergänge aufnehmen, die vom Zustand 1 über Zustand 2 zu Zustand 3 führen? Sprich, muss ich dann die Tabellarische Rechnung so erweitern, dass ich dann sowas machen muss:
R(2,3,1)=c+(a)(c)*(c+c)?
Weiß grad nicht, wie genau ich das ausdrücken soll . . .
Die R(i,j,1) bau ich ja aus den R(i,j,0) zusammen, muss ich dann auch aus R(i,j,1) die R(i,j,2) zusammenbauen also die, die 2 Zustände gehen?
Am besten wäre es, wenn einer da mal vlt. zeigen könnte, wie man da ohne "hingucken", sondern mit der Tabellenrechnung das lösen kann.
Danke im Vorraus!
MfG
|
|
|
01.11.2009 21:58 |
|
|
|
