| Autor |
Beitrag |
Bockscar
      
Beiträge: 105
|
Verfasst: Sa 03.09.05 17:14
Hi. Ich wusste leider nicht genau in welches Forum meien Frage passen koennte. Hat auch nicht direkt etwas mit Delphi zutun, aber da ich hier schon oft Hilfe bekommen habe, versuche ich es erneut.
Ich soll von verschiedenen Zustandsgraphen eines Akzeptor dessen Sprache L(A) ableiten. Habe es bei 5 von 6 Aufgaben auch selbststaendig geschafft, aber das letzte macht mir Probleme.
Ich habe ein Bild des Zustandsgraphen (Paint sei gesegnet  beigefuegt.
Es waere nett, wenn mir jemand bei der Loesung des Problems helfen koennte.
Die Eingabeworte sind wie unschwer zu erkennen X = {a,b}.
Habe ich aber alles eingezeichnet.
Im Vorraus vielen Dank! Moderiert von Gausi: Topic aus Sonstiges verschoben am Sa 03.09.2005 um 18:49
Einloggen, um Attachments anzusehen!
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Sa 03.09.05 17:50
Was ist denn der Startzustand? z0?
Edit: Wenn ja, dann würde ich für L(A) folgendes tippen:
L(A) ist die Menge aller Wörter w aus {a,b}, sodass die Anzahl der a's und die Anzahl der b's in w gerade ist.
_________________ We are, we were and will not be.
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Sa 03.09.05 18:38
???
a^n b^m a^o b^p ; n,m,o,p € |N ; (n mod 2 = 1 => m mod 2 = 1 => o mod 2 = 1 => p mod 2 = 1) || (n+m+o+p mod 2 = 0)
???
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Sa 03.09.05 18:43
@uall@ogc: das reicht imho nicht, da aaabbaaa auch in der Sprache ist. (Die Pfeile gehen ja jeweils in beide Richtungen)
_________________ We are, we were and will not be.
|
|
Bockscar 
      
Beiträge: 105
|
Verfasst: Sa 03.09.05 19:10
also ja z0 ist natuerlich anfangszustand.
Gausi genau das ist das Problem. Aber es muss ne eindeutige Loesung geben ... ich komm da einfach nicht drauf.
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Sa 03.09.05 19:18
Reicht die Beschreibung von oben denn nicht? (Anzahl a gerade, Anzahl b gerade) Muss es wirklich ein regulärer Ausdruck sein?
_________________ We are, we were and will not be.
|
|
Bockscar 
      
Beiträge: 105
|
Verfasst: Sa 03.09.05 20:21
also so weit wie oben habe ich das schon einmal vorgetragen, aber das hat nicht genuegt. Wie saeh es denn als regulaerer ausdruck aus?
Du hast doch selber etwas daran bemaengelt und die aufgabe war ja das wirklich JEDES wort das dargestellt werden kann in der sprache L(A) ist.
wenn z.b aaabbaaa nicht funktioniert, waere es ja nicht voellig richtig.
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: So 04.09.05 11:07
Gausi ich habe nirgendwo die einschränkung gemacht das o oder p nicht 0 sein dürfen
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
Bockscar 
      
Beiträge: 105
|
Verfasst: So 04.09.05 16:51
aber gilt denn 0 mod 2 = 1 ?? gibts das ueberhaupt? ansosnten versteh ich ogc@all sehr gut!
|
|
CenBells
      
Beiträge: 1547
Win 7
Delphi XE5 Pro
|
Verfasst: Mo 05.09.05 10:26
Bockscar hat folgendes geschrieben: | | aber gilt denn 0 mod 2 = 1 ?? gibts das ueberhaupt? ansosnten versteh ich ogc@all sehr gut! |
0 mod 2 ist 0 
_________________ Eine Klasse beschreibt die Struktur und das Verhalten einer Menge gleichartiger Objekte.
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Mo 05.09.05 11:10
2 sachen
1) 0 mod 2 = 0, aber die gleichmung muss ja erfüllt sein d.h. entweder gilt
(n mod 2 = 1 => m mod 2 = 1 => o mod 2 = 1 => p mod 2 = 1) oder
(n+m+o+p mod 2 = 0)
wenn n mod 2 = 1 ist so müssen alle anderen auch ungerade sein, d.h. m,o,p kann gar nicht mehr 0 sein
ist eins von denen gerade so müssen auch alle anderen greade sein
aber!
man kann mit dem automaten auch z.b.
abababab darstellen durch 2 mal durchlaufen, dann gilt obiges immer noch aber es kommt zusätzlich q,r,s,t hinzu genau wie a,b,a,a,b,a
bei z0-z1-z2-z1-z0
was gaussie sagt stimmt soweit, a^x,b^y sind x+y mod 2 = 0
über einzelne parameter kann man das nicht genauer sagen
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
Bockscar 
      
Beiträge: 105
|
Verfasst: Di 06.09.05 14:13
du meinst es kaemen zusaetzlich q,r,s,t hinzu. aber wo genau kommen die hinzu als variablen? versteh deine aussage nicht. ansonsten verstehe ich dich schon.
mfg
nachtrag:
ach du meinnst natuerlich das bei
a,b,a,a,b,a es dann heisst
(n mod 2 = 1 => m mod 2 = 1 => o mod 2 = 1 => p mod 2 = 1 => q mod 2 = 1 => r mod 2 = 1) oder
(n+m+o+p+q+r mod 2 = 0)
right?
|
|
Gausi
      
Beiträge: 8554
Erhaltene Danke: 481
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Di 06.09.05 14:28
Ein Weg, um den regulären Ausdruck für die Sprache zu finden, ist, das zugehörige Gleichungssystem zu lösen. Da der reg. Ausdruck hier nicht so offensichtlich einem ins Auge springt, muss man wohl diesen etwas unbequemen Weg gehen.
_________________ We are, we were and will not be.
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Di 06.09.05 14:31
im endeffekt müssten glaub ich alle exponenten gerade bzw gerade sein
z.b. eindurchlauf jeder exponent (vom zustand) ist 1
dann z.b. einmal ab und dann zurück alle exponenten sind gerade (2,2,0,0)
hat man einen ganzen druchlauf + ab ba (zurück) hätte man 3,3,1,1 (exponeten des zustandes)
alles in allem ist aber die anzahl der a's und b's immer gerade (wie gausi schon sagte)
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
Bockscar 
      
Beiträge: 105
|
Verfasst: Di 06.09.05 14:35
wir hatten die sonstigen zustandsgraphen immer so aehlnich dargestellt
also einer der irgendwie mit a und b anfangen konnte aber mit a aufhoeren musste:
L(A) = { (a^n,b^n)^* a }
das ^* bedeutet dann das es eine kombinations jeglicher laenge vbon a und b sein kann.
aber ich kann ja auch die darstellungsform von ogc@all nehmen
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Di 06.09.05 14:42
dann würd ichs so machen
(a^n b^m a^o b^p)^* n+m+o+p mod 2 = 0
damit sollte man alles darstellen können 
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
Zuletzt bearbeitet von uall@ogc am Di 06.09.05 14:47, insgesamt 1-mal bearbeitet
|
|
Bockscar 
      
Beiträge: 105
|
Verfasst: Di 06.09.05 14:45
aber da ist doch z.b n = 1 und m = 1 dann hat man m+n mod = 0 aber man kommt eben nicht beim ende an ...
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Di 06.09.05 14:47
habs geändert man konnte auch kein ba darstellen ;> also eigentlich bin ich auf das von oben wieder gekommen lol
kann aber auch nicht ich überdenks noch mal eben kurz
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|
Bockscar 
      
Beiträge: 105
|
Verfasst: Di 06.09.05 14:52
wenn eins ungerade ist duerfen die anderen halt nich 0 sein ... sonst gehts nicht weiter ...
(a^n b^m a^o b^p)^* n+m+o+p mod 2 = 0 und (n mod 2 = 1 => m mod 2 = 1 => o mod 2 = 1 => p mod 2 = 1)
|
|
uall@ogc
      
Beiträge: 1826
Erhaltene Danke: 11
Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
|
Verfasst: Di 06.09.05 15:01
Bockstar ich habs mir nochaml durch kopf gehen lassen, so wie du es kennst aufzuschrieben und wie ich es kenne gehts nicht da es eine ineinander verschachtelte rekursion ist, eigentlich kannste alles darstellen wo a und b gerade anzahl sind
aber die definition von L(A) = {xxx} ist denk ich mal ziemlich kompliziert oder ich komm einfach nicht drauf ;>
_________________ wer andern eine grube gräbt hat ein grubengrabgerät
- oder einfach zu viel zeit
|
|