View Full Version : [FRAGE] - Beispiel 3.1
schrankk
26-10-2008, 15:21
Hallo Leute,
eine Frage bzgl. Bsp 3.1: beinhaltet die gegebene Sprache etwa Wörter wie: {aabaab (r=2, w=aab), abc (r=1, w=abc), aaa (r=3, w=a)} ? Also jedes Wort, der mittels *-Operator gebildet wird, plus dazu alle Potenzen dieser Wörter?
vlg
Ein kleiner Tipp w^r = reverse
w = w^r -> Palindrom
Hier mein Vorschlag
schrankk
26-10-2008, 17:04
ach so... nun ist mir die Notation endlich klar!! :thumb:
Den Beweis selbst ist aber mMn nicht besonders schwer, da die Vorgehensweise sowieso immer gleich ist, und es genug solche Bespiele bereits gelöst gibt...
Ich habe so geloest.
Ist es richtig, was denkt ihr darueber? :omg:
Ich habe so geloest.
Ist es richtig, was denkt ihr darueber? :omg:
so wie ich das jetzt auf den ersten blick sehe ist dein wort doch immer noch ein palindrom.
ob du jetzt zb.
aaaabbbcccccccccbbbaaaa
oder dann
aaaabbbcccbbbaaaa
hast, deswegen kannst du es immer noch gleich von hinten nach vorne lesen.
du musst dein y schon so wählen, dass das wort danach wirklich kein palindrom mehr ist.
jperl
achja, anbei wie ich die aufgabe gelöst habe.
sollte ich etwas vergessen oder nicht berücksichtigt haben, dürft ihr mich gerne drauf hinweisen.
ich bitte sogar darum :D
jperl
@jperl
du hast recht :) ich habe es auch jetzt gesehen.
Schoene Loesung danke :)
achja, anbei wie ich die aufgabe gelöst habe.
sollte ich etwas vergessen oder nicht berücksichtigt haben, dürft ihr mich gerne drauf hinweisen.
ich bitte sogar darum :D
jperl
warum hast da für w kein Palindrom genommen, wenn ich fragen darf??
soweit ich weiss ist a^n-i b^i c^i b^i a^n-i kein Wort der Form w=w^r.
warum sollte es kein palindrom sein?
das spiegelbild des wortes ist doch gleich den wort.
jperl
warum sollte es kein palindrom sein?
das spiegelbild des wortes ist doch gleich den wort.
jperl
natürlich, hast recht..sorry
Bianconeri
28-10-2008, 13:55
Habe ich das richtig verstanden, dass ich dafür eigentlich jedes Wort mit |w| >= m verwenden kann, welches in der Sprache liegt, also auch einfach a^m b^n a^m? Damit wäre das ganze ja dann extrem einfach zu zeigen. Denn egal wie man x und y dann wählt, es besteht immer nur aus Symbolen a. Da y nicht das Leerwort sein darf (in diesem Fall also aus mindestens einem a besteht) hat man also mit i = 0 immer ein Wort, welches nicht in L liegt.
schrankk
28-10-2008, 18:25
Habe ich das richtig verstanden, dass ich dafür eigentlich jedes Wort mit |w| >= m verwenden kann, welches in der Sprache liegt, also auch einfach a^m b^n a^m? Damit wäre das ganze ja dann extrem einfach zu zeigen. Denn egal wie man x und y dann wählt, es besteht immer nur aus Symbolen a. Da y nicht das Leerwort sein darf (in diesem Fall also aus mindestens einem a besteht) hat man also mit i = 0 immer ein Wort, welches nicht in L liegt.
ganz genau!!
bei i=1 liegt eigentlich das Wort immer noch in L, sonst für alle i>1 (und wie du richtig geschrieben hast i=0) wird P.L. verletzt!!
achtung das von mir oben gepostete beispiel ist falsch bzw. es beweist nicht ausreichend, dass es sich hier um eine nicht reguläre sprache handelt.
es müsste für alle möglichen fälle bewiesen werden, dass das wort dann kein palindrom mehr ist.
nehmt also besser ein einfacheres wort bei dem es nur eine variante gibt wie von Bianconeri schon angesprochen.
jperl
donpromillo84
28-10-2008, 22:46
@JPerl ... ja, hast recht... much more sweeeeeeeeter :)
thx
achtung das von mir oben gepostete beispiel ist falsch bzw. es beweist nicht ausreichend, dass es sich hier um eine nicht reguläre sprache handelt.
es müsste für alle möglichen fälle bewiesen werden, dass das wort dann kein palindrom mehr ist.
nehmt also besser ein einfacheres wort bei dem es nur eine variante gibt wie von Bianconeri schon angesprochen.
jperl
Aber bei deinem Beispiel kannst du schon zeigen, dass das von dir gefundene Wort nicht in der Sprache liegt. Kann man es nicht wie ein Beweis behandeln ?
mfg
naja zeigen kann man es schon, jedoch muss man dann eben mehrere fallunterscheidungen machen.
zb. kann bei meinem beispiel das y ja in die ersten a's hineinreichen oder nicht, es kann nur a's enthalten bzw. a's und b's. diese fälle müsste man unterscheiden um zu zeigen, dass es keine reguläre sprache ist.
wenn man jetzt aber a^m wählt kann das y nur in a^m liegen (|xy| <= m) und nur a's enthalten.
somit braucht man dann keine fallunterscheidungen machen und der beweis ist mit der wiederlegung dieses falls erbracht.
jperl
also ich beschäftige mich jetzt echt schon lange damit und habs immer noch nicht begriffen! kann mit viell jemand erklären, wie ich xyz wähle (schon klar: |xy|<=m) und vorallem wie das mit den ^i ^j ^k ^l 's funktioniert... und wenns richtig ist am besten am bsp von Bianconeri (http://www.informatik-forum.at/member.php?u=12966): a^m b^n a^m ...was is mein n und wie komm ich zum beweiß?
matthiasb
29-10-2008, 20:59
@chillin
Bin unabhängig von diesem Thread auf den Ansatz w=\underline{a}^{m}\underline{b}^{m}\underline{a}^ {m} gekommen. (Da w=w^{r} darf ich das.)
Jetzt gibts aber für den Opponenten (Skriptum Seite 35f.) nicht die Möglichkeit sein y und x so zu wählen, dass beide zusammen über das erste \underline{a}^{m} hinausragen. (Da ja |yx|\leq m)
All seine Zerlegungen, die der Opponent also durchführen kann beschränken sich auf die Form \underbrace{\underline{a}^{j}}_{x} \underbrace{\underline{a}^{k}}_{y} \underbrace{\underline{a}^{l} \underline{b}^{m} \underline{a}^{m}}_{z} wobei j+k+l=m sein muss.
Mir ist als Proponent gestattet das Teilwort y mit einem beliebigen i\geq 0 zu potenzieren. Ich wähle i=2 und erhalte Folgendes:
\underbrace{\underline{a}^{j}}_{x} \underbrace{(\underline{a}^{k}}_{y})^{2} \underbrace{\underline{a}^{l} \underline{b}^{m} \underline{a}^{m}}_{z}
Wenn ich das dann richtig verstanden habe ist unsere Gleichung j+k+l=m mit unserem i erweitert worden, sodass: j+2k+l=m+k
Weil k aber größer 0 ist (weil y\not= \epsilon) ist die Gleichung auf beiden Seiten größer als m. Damit hätten wir links vom mittig positionierten b^m mehr a als rechts davon, also einen einen Widerspruch, da wir unsere Menge der Palindrome verlassen haben.
Wäre es nicht noch einfacher wenn ich das Wort a^m b a^m nehme?
Sprich ich hab:
a^m b a^m = xyz aus L
xy bestehen nur aus a´s (da |xy| <= m)
y besteht aus mindestens einem a
Wenn ich mir jetzt z.B. den Fall i = 2 anschaue dann ist w:
w = x y^2 z = a^n b a ^m, mit n > m und w nicht in L liegt da es kein Palindrom ist.
Ich bin mir nicht sicher ob ich das so machen kann.
Mfg Czeko
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.