Autor Beitrag
Bockscar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 105



BeitragVerfasst: 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 user profile iconGausi: Topic aus Sonstiges verschoben am Sa 03.09.2005 um 18:49
Einloggen, um Attachments anzusehen!
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 105



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 105



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 105



BeitragVerfasst: So 04.09.05 16:51 
aber gilt denn 0 mod 2 = 1 ?? gibts das ueberhaupt? ansosnten versteh ich ogc@all sehr gut!
CenBells
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1547

Win 7
Delphi XE5 Pro
BeitragVerfasst: Mo 05.09.05 10:26 
user profile iconBockscar 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 105



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 105



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 105



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 105



BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1826
Erhaltene Danke: 11

Win 2000 & VMware
Delphi 3 Prof, Delphi 7 Prof
BeitragVerfasst: 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