Wie sie schon an dem Betreff erlasen, brauche ich Hilfe bei der Theoretischen Informatik.
Wir haben vor 2-3 wochen das Pumping Lemma für reguläre Sprachen eingeführt. Die Definition dazu und die Berechnung habe ich sehr gut verstanden.
Nun kamen wir zu den kontextfreien Pumping Eigenschaften. Die Deifintion davon ist mir auch klar. Wir machten zwar noch keine Berechnung dazu, doch dies ist noch nicht so weiter schlimm.
Nun bekamen wir Aufgaben zu dem Pumping Lemma. Einige davon konnte ich schon lösen, doch bei einigen verzweifle ich.
Ich verzweifle z.B. an den 2 folgenden Aufgaben:
I) Beweisen oder Widerlegen sie: Es gibt eine Sprache, die die reguläre Pumping-Eigenschaft hat, aber nicht die kontextfreie Pumping-Eigenschaft.
II) Beweisen oder widerlegen sie: Jede Sprache, die die reguläre Pumping-Eigenschaft hat, hat auch die kontextfreie Pumping-Eigenschaft.
Können sie mir da helfen? Ich habe hierfür keinen Anhaltspunkt oder so. Einfach auch schon nur die Richtung, welche Aussage richtig und welche falsch ist, wäre super. Vielleicht kommt man dann drauf… naja…vielleicht…
da muss ich Dich leider enttäuschen, ich bin schon etwas zu lange aus dem Thema raus. Kann wikipedia evtl. helfen, ich glaube da waren einmal Beispiele hinterlegt.
wie mir deine mail deutlich gemacht hat, habe ich in den letzten jahren meinen experten-status im bereich theoretische informatik eingebüßt. ich habe mich seit dem studium mit regulären sprachen ect. nicht mehr befasst. leider habe ich nicht die zeit mich mal wieder eingehend zu beschäftigen.
ich kann die fragen also schlichtweg nicht beantworten oder weiterhelfen.
entschuldige die amtsanmaßung ich habe das wer-weiss-was-profil die letzten jahre nicht gepflegt.
ich hoffe ein echter experte hilft dir weiter
gruß
benni
I) Beweisen oder Widerlegen sie: Es gibt eine Sprache, die die
reguläre Pumping-Eigenschaft hat, aber nicht die kontextfreie
Pumping-Eigenschaft.
es gibt auf jeden Fall Sprachen, also die Pumping-Eigenschaft ist nicht
hinreichend für reguläre Sprachen.
Denkbar wäre eine Sprache wie a_m b_n c_n mit m,n>=1. Das a kann man vorne
beliebig aufpumpen. Ist das nichtregulär? Reicht das schon?
II) Beweisen oder widerlegen sie: Jede Sprache, die die
reguläre Pumping-Eigenschaft hat, hat auch die kontextfreie
Pumping-Eigenschaft.
das sollte doch sehr einfach sein: wenn man das uvx der regulären Eigenschaft
hat, dann ist das abcde der kontextfreien doch mit a=u, bcd=v, e=x!? Ich habe da
jetzt nicht genauer darüber nachgedacht, aber so sollte das doch mit kleinen
Änderungen hinkommen.
zunächst kannst Du Dir überlegen, was der aussagenlogische Zusammenhang zwischen I und II ist.
Generell geht man an solche Beweise dann wie folgt heran:
Es gibt zwei Teilaussagen. Für jede Teilaussage gehst Du hin und suchst Sätze und Definitionen heraus, die damit im Zusammenhang stehen. Aus den Sätzen ergeben sich weitere Aussagen. Irgendwann triffst Du auf Aussagen, die im Script bereits bewiesen wurden. Dann musst Du nur noch Äquivalenzumformungen finden die I oder II beweisen oder widerlegen.
Wenn man sich die Chomsky-Hierarchie anschaut, kann man sich leicht überlegen, welche Aussage Wahr und welche falsch ist
Viel Erfolg
Thorsten
I) Beweisen oder Widerlegen sie: Es gibt eine Sprache, die die
reguläre Pumping-Eigenschaft hat, aber nicht die kontextfreie
Pumping-Eigenschaft.
II) Beweisen oder widerlegen sie: Jede Sprache, die die
reguläre Pumping-Eigenschaft hat, hat auch die kontextfreie
Pumping-Eigenschaft.
Vielleicht kommt man dann drauf… naja…vielleicht…
ich habe das wer-weiss-was-profil die letzten jahre nicht gepflegt.