Spitzfindigkeiten
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
9/2003, Aufgabe I-2
Hi,
Die Frage lautet so (solche Fragen kommen anscheinend öfters, ich habe eine Frage allgemein zu diesem Aufgabentyp und nicht zu dieser Frage speziell):
Gegeben: Sprache L mit Defintion
Ist L mit Turing Maschine akzeptierbar?
Ist L kontextsensitiv?
Ist L kontextfrei?
Ist L regulär?
Ich dachte eigentlich, man kann so ziemlich alle Sprachen mit Turing-Maschinen akzeptieren (steht auch so eingerahmt als Satz im Schöning). Hier also immer mit “ja” antworten?
nee, nur bei der ersten frage :-p
wobeis natürlich besser ist, von unten anzufangen 
genau … wenn die Sprache sich als regulär rausstellen sollte, dann kann man ohne nachzudenken die restlichen mit ja beantworten
da ja die regulären Sprachen eine Teilmenge von kontextfreien sind … diese sind eine Teilmenge … u.s.w.
Moin!
Ja meistens steht aber auch noch dabei, dass man alle Antworten begründen soll.
Soll man dann eine Turing-Maschine kontruieren, um zu beweisen dass es geht und dann eine kontextsensitive Grammatik aufstellen, die funktioniert, dann das erweiterte Pumping-Lemma nehmen für die Kontextfreiheit und schließlich das normale Pumping-Lemma für die Regularität?
Ist das nicht viel zu aufwändig?
Da WELL '4
Aber wenn du einmal bewiesen hast, dass die Sprache kontextfrei ist (z.b. durch angeben einer entsprechenden Grammatik), und dann noch zeigst dass das ding nicht regulär sein kann (Pumping lemma), das reicht doch, oder? Die Antwort wäre dann ja, ja, ja, nein.
Ok, dann hast du aber für die ersten drei Fragen immer dieselbe Antwort. Ist zwar richtig, aber geben die dann auch dreimal Punkte dafür? Ich hab da ein mulmiges Gefühl dabei…
Da WELL '4
Also … ich denke einfach “ja” ist zu wenig … da müsste man schon zumindest schreiben … “ja, da die Sprache kontextfrei ist und diese sind eine Teilmenge der Typ 1 und Typ 0 Sprachen” … das wäre dann die gewünschte Begründung … und evtl. noch ein Zusatz “Kontextfreiheit folgt aus Teilaufgabe c”.
solange er nicht schreibt, WIE du es begründen sollst (also etwa TM basteln), kannst du das doch ruhig so machen. richtig ist es auf jeden fall! (und doch auch elegant, du erschlägst ja quasi i∈{1…4} fliegen in einem streich!)
urichichako, hiermit verleihe ich dir den Titel „Theoretischer Informatiker extraordinär“!
Es fehlt nur noch eine bestandene Prüfung in TI :*)
:finger: mit dem titel jetzt müsste ich dann das doch locker schaffen . . . :-/
Ich dachte das pumplemma nimmt man nur wenn man beweisen soll, nicht einfach begruenden. das schaffst du mit folgender aussage naemlich auch aber es ist halt kein aufwendiger pumpbeweis: “dfa = nfa hat keinen Speicher => kann inverse woerter nicht erkennen” sowas siehst du bei den klausuraufgaben naemlich auf anhieb… und man sieht da auch ziemlich gut, dass ein Kellerautomat der mindesttyp an automat ist den man verwenden muss. Weil ich den mit nem LBA simulieren kann und dieser wiederum ne Demoversion einer TuringM ist.
Damit waere ein Begruendung da. (Begruendungen != Beweise Qed)
wo steht denn das genau?
thx
aber es gibt doch auch sprachen, die nicht typ0 sind und damit auch nicht turing-akzeptierbar… trotzdem duerfte die aussage “so ziemlich alle sprachen” dann stimmen.
ja, das stimmt. siehe schoenig seite 20.
sach mers so: wenn da schon ne grammatik steht … :-p