Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » TI-klausur
Autor
Kein bestimmter Bereich J TI-klausur
Nash
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.05.2003
Mitteilungen: 153
  Themenstart: 2004-03-23

Ist sehr wichtig!hab heute Prüfung Kannst mir jemand sagen wann 2 zustände im AKZEPTOR äquivalent sind? meine antwort wäre wenn sie in der selben äquivalenzklasse sind. 0~äquivalenz und k~äquivalenz aber wie geht das wenn ich 2 zustände habe die in verschiedenen akzeptoren sind(Das eingabealphabet ist gleich). Heut nachmittag sag ich euch wie's war.


   Profil
Nash
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.05.2003
Mitteilungen: 153
  Beitrag No.1, vom Themenstarter, eingetragen 2004-03-23

hey verdammt,in einer stunde ist mündliche klausi und keiner will mir helfen...den weg muss ich wohl alleine gehen


   Profil
frosty
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.07.2003
Mitteilungen: 1080
Wohnort: Dresden
  Beitrag No.2, eingetragen 2004-03-23

Ich verstehe nicht mal deine Frage, ich weiß weder was TI ist noch was genau du wigentlich wissen willst...du musst dich schon etwas besser ausdrücken. Viel Erfolg, frosty


   Profil
kelvin
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.06.2003
Mitteilungen: 184
Wohnort: Niedersachsen
  Beitrag No.3, eingetragen 2004-03-23

Hi, tut mir leid, aber geht mir genauso wie Frosty. Ich wuerde Dir gerne mit meinem geballten Wissen aus einem halben Jahr Theoretischer Informatik weiterhelfen, aber wie? Leider weiss ich weder, was ein "Akzeptor" ist (ein Finalzustand, oder eine akzeptierende Berechnung vermute ich mal), noch verstehe ich die Formulierungen mit  "k~äquivalenz" ... bei uns bedeutete "~" immer "ist aequivalent zu". Ich denke am meisten Resonanz wirst Du bekommen, wenn Du deine Fragen etwas ausfuehrlicher umschreibst und dabei sagst, was genau Du nicht verstehst. Bedenke auch, dass es auch uni-/professorenspezifische Formulierungen gibt, die nicht immer fuer alle verstaendlich sind, wie z.B. bei Deinem "Hauptsatz"! Gruß Kelvin


   Profil
Nash
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.05.2003
Mitteilungen: 153
  Beitrag No.4, vom Themenstarter, eingetragen 2004-03-23

so die klausur hab ich hinter mir. Gute nachricht ich habe bestanden,schlechte nachricht ich hab ne 4.0 ohh man,ich könnte so kotzen erste frage. L={p|p element von (abc)^n c} X={a,b,c} kann ich mit diesem alphabet diese Sprache realisieren? ich erstmal überlegt,und dann ja weil X* ja alle wörter enthält die durch a,b,c gebildet werden was hat die sprache für eigenschaften? dann malen sie doch mal eine grammatik dafür auf. so da konnte ich auch dann aber Was sind Syntaxdiagramme?Keine plan ok dann was sind syntaxbäume?? Eine Ableitungsfolge? Falsch! dann einfach abgebrochen was können sie uns über das pumping lemma sagen? und ich AHA dank chronos werd ich dem jetzt mal zeigen was ich drauf hab! definiton gesagt.. und er dann...aha und was sagt der Satz aus? Was ist die Vorraussetzung?? und ich keinen plan gehabt...so und dann gibt er mir eine endliche sprache und ich soll das pumping lemma darauf anwenden L={ab,b} antürlich misslungen und was war die Vorraussetzung?? Die srpache muss Unendlich gross sein!!!!!Das steht nicht mal im Hopcroft drinn!fuck und dann halt noch wann sind 2 zustände im automaten äquivalent? das könnte ich zum glück es war eigentlich machbar mit eine 1.0 nach hause zu gehen,aber ich habs halt nicht drauf so jetzt kann ich TI vergessen ;-)


   Profil
Ehemaliges_Mitglied
  Beitrag No.5, eingetragen 2004-03-23

Mehr als mein Mitgefühl kann ich Dir leider nicht anbieten, John.


   Profil
Ehemaliges_Mitglied
  Beitrag No.6, eingetragen 2004-03-30

Dass das PL nur für unendliche Sprachen gilt, stimmt so glaube ich nicht, aber: In einer endlichen Sprache gibt es ja ein Wort mit maximaler Länge. Wenn das n des PL nun größer ist als diese maximale Länge, so ist die Aussage des PL ja leer (es gibt kein w mit |w|>n) also hilt das PL nix. Gruss Chronos


   Profil
kelvin
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.06.2003
Mitteilungen: 184
Wohnort: Niedersachsen
  Beitrag No.7, eingetragen 2004-03-30

ich wuerde sagen, dass die Idee, an einer endlichen Sprache herumzupumpen schon falsch ist. Der Beweis, dass die Sprache regulaer ist, muss gar nicht gefuehrt werden, denn man kann fuer jede endliche Sprachen ja einen Automaten finden, der genau die Sprache akzeptiert. Gruß Kelvin


   Profil
Buri
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.08.2003
Mitteilungen: 46551
Wohnort: Dresden
  Beitrag No.8, eingetragen 2004-03-30

Hi alle, es wäre fein, wenn mal jmd einen fundierten Artikel über das PL (ja, ihr wißt's schon, das Pumping Lemma) schreiben würde. Ich weiß darüber gar nix, ich höre nur immer "reguläre Sprachen" usw. Wer traut sich? Gruß Buri


   Profil
hirngeschwandter
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 14.10.2003
Mitteilungen: 1063
Wohnort: Darmstadt (z.Z. in Dresden)
  Beitrag No.9, eingetragen 2004-03-31

Hallo, ich würde mich zwar trauen, "schulde" Matroid aber immer noch einen Artikel über nicht-klassische Logiken *g*. Gruss Enno


   Profil
wasseralm
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.10.2003
Mitteilungen: 1838
Wohnort: Erlangen
  Beitrag No.10, eingetragen 2004-03-31

Hallo, ich hätte evtl.Interesse, kann aber momentan nicht sagen, wann ich Zeit dafür finde. Gruß von Helmut


   Profil
michf
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 11.09.2003
Mitteilungen: 341
Wohnort: München
  Beitrag No.11, eingetragen 2004-03-31

Hi! Ich würde wahnsinnig gern einen Artikel über das Pumping Lemma schreiben. Ich bin schließlich seit Januar Diplom Informatiker (Univ.) ;-) und habe schon viel mit dem Pumping Lemma zu tun gehabt. Vielleicht schreibe ich gleich einen Artikel über reguläre und kontextfreie Sprachen (evtl. auch kontextsensitive Sprachen) und das Pumping-Lemma. Hat jemand Lust mir zu helfen? Ich will auch einige Übungs- (und Beispiel-)aufgaben behandeln. Gruß, Michael


   Profil
wasseralm
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.10.2003
Mitteilungen: 1838
Wohnort: Erlangen
  Beitrag No.12, eingetragen 2004-03-31

Hallo Michael, ich bitte mich schon einmal als Reviewer an (wenn du Interesse daran hast) . Gruß von Helmut


   Profil
kelvin
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.06.2003
Mitteilungen: 184
Wohnort: Niedersachsen
  Beitrag No.13, eingetragen 2004-03-31

2004-03-31 16:55: michf schreibt: bin schließlich seit Januar Diplom Informatiker (Univ.) ;-) und habe schon viel mit dem Pumping Lemma zu tun gehabt. cool, kannst Du mir vielleicht sagen, wie ich mir das dann spaeter vorzustellen habe? Wo finden denn konkret die Inhalte aus der theoretischen Informatik Anwendungen im Berufsleben? Bei Automaten ist klar, dass man das braucht (Zustandsdiagramme, CPU-Funktion), aber Sprachen und Turingmaschinen waren fuer mich bisher immer ein Berechnungsmodell, um zu zeigen, was berechenbar ist und was eben nicht. Was haben die noch fuer weitere Funktionen und wie kann ich mir die Anwendung vorstellen? Vielen Dank schonmal! Gruß Kelvin


   Profil
Nash
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.05.2003
Mitteilungen: 153
  Beitrag No.14, vom Themenstarter, eingetragen 2004-03-31

hui kelvin,sagt dir compilerbau was? Bei TI gehts ja eigentlich "nur" daruam eine unendliche sprache in eine andere unendliche sprache zu übersetzen,korrekt. Z.B. C Befehle in 011010011. Kontextunabhängige Sprachen werden dafür benutzt. Wie überprüft man von unendlich vielen C Algorithmen das es ein korrektes C programm ist?Tja und diese Frage wird bei TI beantwortet.


   Profil
kelvin
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.06.2003
Mitteilungen: 184
Wohnort: Niedersachsen
  Beitrag No.15, eingetragen 2004-03-31

Hi, nein bei Compilerbau bin ich leider noch nicht angelagt. Und ehrlich gesagt sehe ich den Zusammenhang zwischen Programmiersprache und Maschinensprache in Bezug zu TI auch nicht ganz. In wie weit geht es denn darum, Sprachen zu "uebersetzen". Man uebersetzt doch nicht regulaere Sprachen in kontextfreie, oder habt ihr sowas gemacht? Gruß Kelvin edit: vielmehr glaube ich nicht, dass man rekursive in regulaere/kontextfreie Sprachen uebersetzen kann. Dass Automaten Berechnungen auf Compilerebene darstellen koennen und Turingmaschinen Sprachen auf Programmiersprachenebene ist klar, aber wo genau ist denn der Zusammenhang zwischen beiden? [ Nachricht wurde editiert von kelvin am 2004-04-01 10:55 ]


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Ehemaliges_Mitglied
  Beitrag No.16, eingetragen 2004-04-01

Naja, fuer Turing-Maschinen gibts ja auch die Darstellung als endlicher Automat(->Zustaende und Transitionen). Der Unterschied besteht darin, dass TM im Gegensatz zu Akzeptoren noch ein "Gedaechtnis in Form des Bandes/Baender haben".


   Profil
kelvin
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.06.2003
Mitteilungen: 184
Wohnort: Niedersachsen
  Beitrag No.17, eingetragen 2004-04-01

2004-04-01 12:11: Olli1983 schreibt: Naja, fuer Turing-Maschinen gibts ja auch die Darstellung als endlicher Automat(->Zustaende und Transitionen). Es kann doch aber nicht fuer jeden Turingmaschine M ein Automat A gefunden werden mit L(A) = L(M). Zum Beispiel findet man leicht eine TM fuer die Sprache L = {a n bn cn}. Diese Sprache ist aber nicht kontextfrei und deshalb kann es keinen Automaten geben, der die Sprache akzeptiert.


   Profil
ChrisH
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.08.2003
Mitteilungen: 295
Wohnort: Potsdam
  Beitrag No.18, eingetragen 2004-04-01

Hi, sagt mal, das Pumping Lemma kann doch gar nicht für endliche Sprachen L gelten, weil es doch heißt, das für jedes Wort z der Sprache, geschrieben als uvw + ein paar Bedingungen (abs(v) >= 1 usw.), gelten muss, dass uv^i w für ALLE i >= 0 (in \IN )in L ist. Damit muss ja für die Kardinalität der Sprache auf jedenfall >= card(\IN) gelten. mfg Chris


   Profil
wasseralm
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.10.2003
Mitteilungen: 1838
Wohnort: Erlangen
  Beitrag No.19, eingetragen 2004-04-01

Hallo Chris, das PL gilt schon für alle endlichen Sprachen, denn es sagt ja, dass es ein n gibt derart, dass für alle Wörter w der Sprache mit |w| > n eine bestimmte Eigenschaft gilt. Wählt man n größer als ide maximale Länge eines Wortes der Sprache, dann ist dies automatisch erfüllt. Gruß von Helmut P. S. Jede endl. Sprache ist zudem regulär.


   Profil
ChrisH
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 08.08.2003
Mitteilungen: 295
Wohnort: Potsdam
  Beitrag No.20, eingetragen 2004-04-01

Hallo Wasseralm, achso, also man betrachtet das als Implikation. Ja ok dann stimmts ;-) mfg Chris


   Profil
Das Thema wurde von einem Senior oder Moderator abgehakt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]