4 Antworten zu dieser Frage

1. Antwort von nach 2 Stunden 0 hilfreich

   Re: theoretische Informatik

   hallo clodan,
   
   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
   

2. Antwort von nach 5 Stunden 0 hilfreich

   Re: theoretische Informatik

   Sorry, keine Ahnung... Schönen Guten Tag!
   
   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...
   
   
   Vielen Dank schon einmal für die Hilfe. :)
   
   
   MFG Clodan
   

3. Antwort von nach 8 Stunden 0 hilfreich

   Re: theoretische Informatik

   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. Können sie mir da helfen?
   Ich hoffe, das hilft.
   
   gruss, mofte
   

4. Antwort von nach 17 Stunden 0 hilfreich

   Re: theoretische Informatik

   Hallo Clodan,
   
   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.
   
   

   Jetzt auf diese Frage antworten.