View Full Version : [FRAGE] - Alte Prüfungsbeispiele
Hat jemand schon alte Prüfungsbeispiele (zu finden unter http://www.logic.at/lvas/thinf1/index.shtml#prangab, http://www.logic.at/lvas/eti/#prangab bzw. http://www.logic.at/lvas/ti/#prangab) gelöst? Würde gerne meine Lösungen vergleichen bzw. diskutieren.
Angabe zu finden unter http://www.logic.at/lvas/eti/angaben/etiv022.pdf
Lösungsvorschlag als Attachment ...
hmm komisch, dein Automat hat schon mal ein ganz anderes Alphabet als die Angabe... sicher, dass du nicht die falsche Angabe gepostet hast? beim Beispiel 5 geht es dort ja um die Sprache
{c^n d e^n+m f g^m | n,m>0}
hmm komisch, dein Automat hat schon mal ein ganz anderes Alphabet als die Angabe... sicher, dass du nicht die falsche Angabe gepostet hast? beim Beispiel 5 geht es dort ja um die Sprache
{c^n d e^n+m f g^m | n,m>0}
schon korrigiert!
deine Lösung sieht ziemlich korrekt aus ;) wobei ich vielleicht auch X nicht durch ein blanc-Symbol, sondern durch ein anderes Symbol (a oder so) ersetzen würde - mit dem blanc-Symbol gehts zwar auch, ich fände es so nur halt eleganter :)
deine Lösung sieht ziemlich korrekt aus ;) wobei ich vielleicht auch X nicht durch ein blanc-Symbol, sondern durch ein anderes Symbol (a oder so) ersetzen würde - mit dem blanc-Symbol gehts zwar auch, ich fände es so nur halt eleganter :)
das mit dem blanc-Symbol hab ich mir auch überlegt - ich denke der Vorteil im Ersetzen des X durch ein blanc liegt darin, dass dadurch die Ableitung kürzer wird.
der Vorteil vom Symbol dagegen ist, dass, wenn du die Maschine erweitern/modifizieren willst die Information über die Anzahl der X nicht verlorengeht (man kann mit Turing-Maschinen ja mehr machen, als nur zu prüfen, ob ein Wort in einer Sprache ist). ok, diesem Fall lässt sich das im Nachhinein immer noch nachvollziehen - es sind ja genau dreimal so viele, wie du hakerln zwischen den beiden '+' hast.
Aber im allgemeinen bevorzuge ich es, die Information gar nicht erst verloren gehen zu lassen.
Angabe unter http://www.logic.at/lvas/eti/angaben/etiv021.pdf
Lösungsvorschlag als Attachment ...
der Vorteil vom Symbol dagegen ist, dass, wenn du die Maschine erweitern/modifizieren willst die Information über die Anzahl der X nicht verlorengeht (man kann mit Turing-Maschinen ja mehr machen, als nur zu prüfen, ob ein Wort in einer Sprache ist).
Das stimmt natürlich!
Zu entscheiden bleibt damit: schneller Algorithmus oder kein Informationsverlust ;).
Ich hab zuerst einen anderen Ansatz probiert, aber deiner ist kürzer :) meine Idee wär gewesen, den "klassischen" a^n b c^n Automaten "umzukehren" (also von links nach rechts vorgehen statt von rechts nach links - braucht man weil ja die 'C's zuerst "aus" sein müssen) und dann zu prüfen, ob es noch ein 'A' gibt... ist aber wie gesagt länger und außerdem unintuitiv, weil wir das von-links-nach-rechts nicht gewohnt sind...
allerdings scheinst du einen besonderen Hang zu blanc-Symbolen zu haben ;) aber wie gesagt, richtig ist es eh auch.
edit:
Zu entscheiden bleibt damit: schneller Algorithmus oder kein Informationsverlust
Er wird nicht langsamer. Der einzige Unterschied ist ja, dass du bei den Übergängen von 1->2 , 2->3 , 3->4 und 9->1 statt dem blanc-Symbol ein 'A' (oder was auch immer) verwendest. Und ein 'A' zu lesen oder zu schreiben geht nicht schneller und nicht langsamer als ein blanc zu lesen bzw. zu schreiben.
Angabe unter http://www.logic.at/lvas/eti/angaben/etiv023.pdf
bei dem hänge ich gerade :confused: ...
bin schon auf der Spur :ausheck: ...
sollte so passen :D :
ich hätts so gemacht: ich geh zuerst zum x, dann geh ich nach rechts, ersetze einen 0er durch ein 'b'. Dann geh ich zurück zum Anfang. lösche den ersten '1'er, ersetze dann den letzten '1'er durch ein 'a'. Wenn ich alle '1'er abgearbeitet hab, ersetze ich alle 'a's wieder durch '1'er. Wenn kein '0'er da ist, muss links noch genau ein '1'er stehen.
Ich hab leider keinen Scanner da, sonst könnt ich dir meinen Vorschlag etwas konkreter zeigen...
ich hätts so gemacht: ich geh zuerst zum x, dann geh ich nach rechts, ersetze einen 0er durch ein 'b'. Dann geh ich zurück zum Anfang. lösche den ersten '1'er, ersetze dann den letzten '1'er durch ein 'a'. Wenn ich alle '1'er abgearbeitet hab, ersetze ich alle 'a's wieder durch '1'er. Wenn kein '0'er da ist, muss links noch genau ein '1'er stehen.
Ich hab leider keinen Scanner da, sonst könnt ich dir meinen Vorschlag etwas konkreter zeigen...
bin gerade beim Verifizieren meiner Lösung. Bis jetzt passt's. Die Maschine lässt sich von der Turing-Maschine Abb3 (http://www.logic.at/lvas/thinf1/skriptum/turing.pdf) ableiten.
Bin mir nicht sicher ob dein Prinzip hinhaut - hast du dir überlegt, dass die '1' mit 2^n wachsen (also bei 3 '0'er 8 '1'er, bei 4 '0'er 16 '1'er, ...). Du musst ja auch darauf achten, dass das Wort in der Sprache liegt.
na für jeden '0'er nehm ich die hälfte der '1'er raus, und zum Schluss muss genau ein '1'er übrigbleiben. Das heißt also eben, dass ich für n '0'er genau 2^n '1'er haben muss.
Was hast du denn geglaubt, was mein Prinzip tut? ;)
edit: wie funktionniert deine Maschine eigentlich?
im Prinzip gehe ich eh auch ähnlich dem Beispiel in der Skriptum-Ergänzung vor: ich ersetze einen '0'er und dann entferne ich entsprechend viele '1'er. Das einzig kompliziertere an diesem Beispiel hier, ist, dass man herausfinden muss, wie man die Hälfte der '1'er löscht... und ich mache das. indem ich immer die erste '1' lösche, die letzte durch ein 'a' ersetze, und immer so weiter, bis ich nur noch blancs und 'a's da stehen habe - und dann ersetze ich die 'a's wieder durch '1'er. Dann hab ich nämlich genau halb so viele '1'er da stehen wie vorher.
Übrigens ist mir grad was aufgefallen, ich hab eigentlich immer die hälfte der '1'er durch blancs ersetzt, weil ich gedacht hab, es wär komplizierter, wenn ich ein neues Symbol nehmen würde... aber eigentlich ist es eh nicht komplizierter... ich hätte ruhig ein eigenes Symbol statt den blanc nehmen können.
na für jeden '0'er nehm ich die hälfte der '1'er raus, und zum Schluss muss genau ein '1'er übrigbleiben. Das heißt also eben, dass ich für n '0'er genau 2^n '1'er haben muss.
Was hast du denn geglaubt, was mein Prinzip tut? ;)
hab's kappiert - so läuft meine Lösung auch
edit: wie funktionniert deine Maschine eigentlich?
Lösung ist in meinem Post mit der Angabe drinnen.
meine Lösung geht ein bisschen anders, aber das Prinzip ist dasselbe. Ich verzichte aber auf den Krampf, dass genau jeder zweite '1'er gekillt wird, sondern lösche immer den ersten, ersetze den letzten durch ein 'a'. Gut, genaugenommen handle ich mir dadurch erst recht einen Krampf ein, weil ich die 'a's wenn ich fertig bin wieder in '1'er "zurückverwandeln" muss... aber das geht eh mit einem einzigen Zustand.
allerdings hab ich zum Schluss dann doch zwei Zustände mehr (ich brauche 4 Zustände um zum Schluss zu kontrollieren, ob, wenn kein '0'er mehr da ist, auch wirklich nur noch ein '1'er da ist)
Der eigentliche Hauptteil ist bei mir gleich lang.
ah ja... machst du eigentlich nur Turingmaschinenbeispiele?
ah ja... machst du eigentlich nur Turingmaschinenbeispiele?
Nein, hab' nicht vor schnellster Löser von Turing-Maschinen-Beispielen zu werden. Bin nur heute bei dem Thema gelandet ... (und ein wenig Gegenchecken steigert wenn's passt das Selbstvertrauen).
Habe zu (min.) DEAs und Grammatiken auch schon ein paar Aufgaben fertig (für die sind aber ohnehin großteils von den Profs. die Lösungen auch im Netz).
Angabe unter http://www.logic.at/lvas/eti/angaben/etiv034.pdf
Lösungsvorschlag:
Angabe unter http://www.logic.at/lvas/eti/angaben/etiv034.pdf
Lösungsvorschlag:
Angabe unter http://www.logic.at/lvas/eti/angaben/etiv034.pdf
Lösungsvorschlag:
Angabe unter http://www.logic.at/lvas/thinf1/angaben/ti1v027.pdf
Lösungsvorschlag:
Sequentialkalkül hab ich mir angeschaut... dürfte passen.
Grammatik schaut auch ok aus.
die anderen zwei hab ich noch nicht angeschaut.
Angabe unter http://www.logic.at/lvas/thinf1/angaben/ti1v027.pdf
Lösungsvorschlag:
Angaben unter
http://www.logic.at/lvas/eti/angaben/etiv033/1.jpg bzw. http://www.logic.at/lvas/eti/angaben/etiv033/2.jpg
Lösungsvorschlag:
Angabe unter: http://www.logic.at/lvas/eti/angaben/etiv034.pdf
Lösungsvorschlag als Attachment (ich hoff, das ist noch lesbar) ...
vBulletin® v3.7.1, Copyright ©2000-2009, Jelsoft Enterprises Ltd.