Variablen ableiten mit 2 Strings

[Houly]

Hallo,

ich möchte eine Variable c zu d ableiten, dabei gibt es folgende Regeln:

c -> a a b c a ,
c -> a c b
c -> b c b a a

b c b -> d
a d a -> d
b d b -> d

Das heißt also, dass "c" meine Startvariable ist und daraus folgt z.b. aabca und aus dem c darin wird wieder eine Regel angewendet bis mal nur noch d übrig ist.
Meine Idee war 2 Strings (ein für c und ein für d) mit der Feldgröße 3 jeweils. Sodass dann alle Kombinationen an Regeln durchprobiert werden bis er mal nach d abgeleitet hat. Kann man die Strings vergleichen irgendwie, sodass die Regeln angewendet werden?

Gruß

 

[Geeeee]

Das Problem ist ja hier, dass deine Regeln in "unendlicher" Tiefe anwendbar sind. Ich kann immer wieder z.B. die erste Zeile aufrufen. Hast du schon einen Algorithmus dafür? Ich sehe das geringste Problem im Datentyp. Für deine Sachen an sich würden sich auf jeden Fall Regexp anbieten. Gehe auch davon aus, dass es nicht ohne Rekursion geht (oder du machst nach einer gewissen Anzahl von Versuchen automatisch Schluss)

 

[Marco13]

Jo, pragmatisch wäre: Solange mit RegEx drauf rumprügeln, bis sich durch die Anwendung IRGENDeiner der Regeln nichts mehr ändert... Besonders effizient wäre das nicht, auch nicht "elegant" oder "schön" (zumindest aus meiner Sicht), aber alles, was darüber hinausgeht, kann eben beliebig weit darüber hinausgehen. Du willst ja keinen ""Compiler"" schreiben....

 

[SlaterB]

@Houly
in diesem Fall wäre das gar nicht unbedingt nötig, alles hängt nur von c ab,

wenn du immer nur c im Blick hast, dann könntest du mit den obigen Regeln einen linken und rechten Rest auffüllen, so lange du willst:
Anfang c
wähle Regel 1
-> linker Rest aab, rechter Rest a
wähle Regel 2
-> an linken Rest a anfügen, an rechten Rest b anfügen
(es bietet sich an, den rechten Rest verkehrt herum aufzuschreiben, da es meist leichter ist, von rechts etwas anzufügen und wieder zu entfernen, bei Listen z.B.)
usw.
immer nur die Reste vergrößern,

wenn dann die unteren drei Regeln kommen, fallen die obigen drei sowieso weg, es bleibt immer noch alles beim c bzw. d hängen:

Regel 4 (nur einmal anwendbar, falls noch c vorhanden)
-> c durch d ersetzen, beim linken Rest b entfernen, beim rechten Rest b entfernen
Regel 5, 6
-> d unverändert, wieder nur linken + rechten Rest kürzen

die beiden Reste z.B. als Listen von Character oder auch speziellen Objekten, eine Enum z.B.,
StringBuilder vielleicht

--------

im allgemeinen Fall Speicherung fast genauso, auch z.B. ne Liste/ StringBuilder für die Zeichen, String selber wäre unnötig aufwendig,
darin dann per Schleife nach einem Suchmuster suchen,
wenn erstes Zeichen gefunden, prüfen ob die anderen dahinterkommen,

bei Bedarf entfernen und durch neue ersetzen

da hier sehr viel verschoben werden muss (wenn man ein Zeichen aus der Mitte einer Liste löscht, rücken alle weiteren eine Position nach),
kann man aus Performancegründen eine LinkedList statt ArrayList verwenden

edit: String mit Substring und indexOf-Suche und Replace und RegEx wäre einfacher, aber aufwendig

 

[Houly]

Hallo!

Danke für die Ideen.
Mit Regex habe ich mich noch nicht befasst.
Habe gerade mal kurz darüber geschaut. Split is bedeutet wo das er eine Rekursionsebene tiefer geht?
Mal grob durchdacht, kann ich sagen das man wo ca.~80 mal die 'c' Regeln anwenden muss und das soweit aufblässt das ein Palindrom entsteht. Dann wird die d 'Regel' so oft angwendet bis nur noch d übrig ist. Ich rechne mal mit 130 Schritten Gesamt.

@SlaterB
Danke klingt ganz gut, nur ich muss erstmal deine Denkweiße umsetzen.
Das ist mit mein Java Grundlagen grad etwas schwierig dafür jetzt einen Algorithmus
so schnell zu programmieren, aber ich schau mal weit ich das umsetzen kann

 

[0x7F800000]

Öhm... Leute, ihr habt ja Probleme^^
Was redet ihr hier von regex und sonstwas, wenn die Grammatik mehrere Nichtterminale auf der rechten seite hat, und dazu nicht monoton ist? Das ist doch Typ-0. :shock:
Da ist das Wortproblem nicht entscheidbar... Vielleicht hat man bei "d" Glück, und es gibt irgendeine kurze Produktionsfolge, die ein "d" liefert, aber das wäre eher Glück, weil man eigentlich unendlich lange zwischenergebnisse erzeugen kann, die dann wieder zu einem einzelnen Symbol kollabieren... Man kann hier also nicht direkt garantieren, dass ein Zwischenschritt nicht 2^10000 symbole enthält :noe: Aber eigentlich ist es durch elementare allegemein anwendbare ableitungsalgos nicht möglich...

Ob man hier durch scharfes Hinguggen & einfache Induktion entdecken kann, dass d nicht ableitbar sein kann, ist eine andere Frage, die ist aber nicht mehr mit java, sondern ausschließlich mit papier und bleistift und Gehirn zu lösen... Mal schauen...:rtfm:

 

[0x7F800000]

Oh, übrigens, ist in der tat völlige trivialität...

c -> a a b c a 
c -> a c b  
c -> b c b a a
 
b c b -> d
a d a -> d
b d b -> d

An der zweiten Hälfte erkennt man direkt, dass ausschließlich Palindrome der form
SbcbR [wobei S,R aus {a,b}* mit S=reverse(R) ]
akzeptiert werden

[ACHTUNG: SCHROTT!]
Angenommen d wäre ableitbar, dann müsste man mit der ersten Produktion beginnen, da bei der 2. und 3. die Randsymbole nicht übereinstimmen. Die erste Produktion hat aber 3 a's und nur ein b => nicht symmetrisch. Dies lässt sich durch keine andere Produktion ausgleichen, da alle andere Produktionen immer gleiche Anzahl von a's und b's enthalten. Also lässt sich kein solches Palindrom produzieren, also ist insbesondere d nicht ableitbar, qed.


Das da:

Mal grob durchdacht, kann ich sagen das man wo ca.~80 mal die 'c' Regeln anwenden muss und das soweit aufblässt das ein Palindrom entsteht. Dann wird die d 'Regel' so oft angwendet bis nur noch d übrig ist. Ich rechne mal mit 130 Schritten Gesamt.

scheint mir also keine besonders gute Schätzung zu sein... :noe:

Java kann in diesem Fall voll nach hause gehen, wie so ziemlich jede andere Programmiersprache auch... :autsch:

Ich hoffe jetzt mal, dass es keine Hausaufgabe gewesen ist?

 

[Leroy42]

@Houly
in diesem Fall wäre das gar nicht unbedingt nötig, alles hängt nur von c ab,

wenn du immer nur c im Blick hast, dann könntest du mit den obigen Regeln einen linken und rechten Rest auffüllen, so lange du willst:
Anfang c
wähle Regel 1
-> linker Rest aab, rechter Rest a
wähle Regel 2
-> an linken Rest a anfügen, an rechten Rest b anfügen
...

In Ordnung, aber ich vermute mal, daß der OP ein Programm
für die Allgemeinheit sucht und daß seine Produktionen nur
ein Beispiel darstellen sollen :shock:

 

[Houly]

Das da:

scheint mir also keine besonders gute Schätzung zu sein... :noe:

Java kann in diesem Fall voll nach hause gehen, wie so ziemlich jede andere Programmiersprache auch... :autsch:

Ich hoffe jetzt mal, dass es keine Hausaufgabe gewesen ist?

Es ist eine freie Selbststudienaufgabe. Ich habe vor 2 Wochen mal mit Zettel und
Stift angefangen, aber kam nie auf eine Lösung. Die Professorin meinte es wäre lösbar,
aber nicht mit Hand, weil es zuviele Schritte sind. Deshalb wollte ich mal ein Programm dafür schreiben! Die Idee von SlaterB finde ich aber nicht schlecht. Ich würde es jetzt mal so probieren das ich 2 Strings erstell einen vor dem c und einen danach.
Das Programm soll dann aufhören sobald beide Strings gleich sind und ich verwende nur die 1. Regel beim c. Wenn es das löst, dann kann man manuell die d Regeln ja anwenden und es auflösen. Ich weiß das es nicht die effizienteste Variante ist

gruß

 

[0x7F800000]

Das Programm soll dann aufhören sobald beide Strings gleich sind und ich verwende nur die 1. Regel beim c.

Wenn du nur die erste regel verwendest, dann ist es ja wohl offensichtlich, dass der linke String vor dem c immer drei mal so lang ist, wie der rechte...

Wenn es das löst, dann kann man manuell die d Regeln ja anwenden und es auflösen.

Öhm... hast du am Beweis in meinem letzten Beitrag irgendwas auszusetzen [außer dass es vielleicht nicht übertrieben formal aufgeschrieben wurde]? ???:L Falls nicht, dann bleibt hier nun mal kein Platz für Vermutungen, Schätzungen, Hoffnungen, Glauben oder ähnliche Sachen: d ist nicht ableitbar, fertig. Da kannst du dir Tausend programme schreiben, ableitbarer wird's dadurch nicht.

Die Professorin meinte es wäre lösbar

Dann hat die Professorin beim flüchtigen Drüberschauen vielleicht irgendwo ein 'b' übersehen, oder du hast in deinem ersten Post irgendwas verdreht, oder ich hab grad Brett vor'm Kopf und sehe meinen Fehler nicht. Wenn einer den Fehler sieht, so möge er mir doch bitte verraten wo... ???:L

 

[SlaterB]

noch nicht vollständig:

> Dies lässt sich durch keine andere Produktion ausgleichen, da alle andere Produktionen immer gleiche Anzahl von a's und b's enthalten.

wie meinst du das? es müssen doch nicht gleich viele a's wie b's sein, wenn rechts noch zwei weitere a's dazukommen,
dann wäre es wieder gut,

nach insgesamt 2x Regel 1 und 1x Regel 2 hat man
aabaaba c baa

also die äußeren aab von der ersten Regel 1 abgearbeitet,
dafür freilich mit nun links überstehendend aaba wohl ein größeres Problem,
aber es gibt ja durchaus Regeln, die rechts mehr a's und b's erzeugen als links,
z.B. einmal Regel 3 ergibt neu
aabaabab c baabaa

also praktisch nur noch
ab c

um dieses ab abzubauen geht nur Regel 1 + Regel 3
->
abaaba c ba

damit hat man links wiederum aaba überstehend, das ist schon bekannt,


jetzt kann man noch mit den anderen Regeln weitermachen,
wird aber auch 'nicht lösbar' herauskommen, nur bisschen komplizierter?

 

[0x7F800000]

wie meinst du das? es müssen doch nicht gleich viele a's wie b's sein, wenn rechts noch zwei weitere a's dazukommen

akzeptiert. hatte einen denkfehler, mein beweisversuch von eben ist schrott, danke SlaterB.
Hab mir da zwischendurch irgendwas total kompliziertes ausgedacht, da kam es später irgendwie zu einem kurzschluss... Damn it^^ :autsch:

wird aber auch 'nicht lösbar' herauskommen, nur bisschen komplizierter?

So, jetzt bin ich aber verärgert und will's genauer wissen^^ Ich tüftle mal noch ein bisschen.

 

[Houly]

...Ich tüftle mal noch ein bisschen.

Mach dir nicht zuviel arbeit, glaub dafür is die zeit zu schade und man kann sinnvollere Programme schreiben
Ich habe es mittlerweile erstmal eingestellt. Habe eben mit einen Komilitone geredet. Er hat es in Delphi umgesetzt und das Programm rechnet nun seit einer Woche auf nem Linux Server und is immer noch nich am Schluss

Mal eine kleine Off-Topic Frage, falls das kurz ok ist.
Den ganzen Tag Bücher über Java lesen oder sich Video2Brains anzuschauen ist ja auch nich das wahre. Man muss ja auch praktisch mal was probieren um zu weiter zulernen.
Hat jmd einen Vorschlag was man praktisch als Anfänger so schreiben kann?

Gruß

Edit: @0x7F800000: Falls Du noch zu einer neuen Erkenntnis/Ergbenis gekommen bist, kannst ja trotzdem mal berichten! ; )