Gute Ressourcen über Berechnungsmodelle zu lernen?

Question

Aus Neugier, versuche ich, zu identifizieren, was Rechenmodell ein System I Arbeit mit funktionell gleichwertig ist, und die Gleichwertigkeit nachzuweisen. Je länger ich verbringen zu diesem Problem mehr das ich vermute, dass das System nicht Turing-Äquivalent. Mein Verständnis von Turing-Maschinen und rekursiv aufzählbar Sprachen ist gut, aber ich weiß nicht viel über Automaten mit geringeren Fähigkeiten (zum Beispiel Kellerautomaten), so bin ich nicht sicher, wie es weitergeht.

Als erstes kann jemand eine gute Ressource für das Lernen über verschiedene Berechnungsmodelle empfehlen? Ich habe Interesse an Grammatiken, Sprachen und Automaten, und wie Gleichwertigkeit und Unterschied zwischen ihnen allen zu beweisen. Im Idealfall würde die Ressource brechen alle Elemente der einzelnen Modelle im Detail und vergleichen sie.

Zweitens ist es eine allgemeine Ausrichtung oder Rahmen, die verwendet werden sollen, wenn ein System auf jedem dieser Rechenmodelle zu passen versuchen?

Answer 1

würde ich ein gutes Lehrbuch der Informatik empfehlen (In meiner Uni Natürlich studiere ich von Sipser der Einführung in die Theorie der Berechnung , die meiner Meinung nach sehr gut. Sie können auch eine free Lehrbuch , die gleich lehrt, aber ich habe keine Erfahrung mit einer so dass ich nicht empfehlen kann).

Der andere Ansatz würde wahrscheinlich nur sein, auf Wikipedia zu lesen. Sie können tatsächlich eine Menge Kilometer aus dem Wikipedia-Artikel erhalten, wenn Sie wissen, was Sie in welcher Reihenfolge suchen. Auch, wenn etwas unklar ist, können Sie in der Regel Google es und mehr Ressourcen zu diesem speziellen Thema.

Natürlich ist dieser Wille nicht sein so gut wie ein echtes Lehrbuch, aber es ist ein guter Ort, um zu beginnen jetzt , und es ist kostenlos.

Als Ausgangspunkt, ich würde empfehlen, zu den folgenden Themen zu lesen (in der aufgeführten Reihenfolge):

1. deterministischen endlichen Automaten
2. Nichtdeterministische Finite Automaton und ihre Übereinstimmung mit dem DFAs.
3. Regular Sprachen und ihre Übereinstimmung mit dem DFAs.
4. Automata Push-Down
5. kontextfreie Grammatiken und ihre Übereinstimmung mit der Push-Down-Automata.
6. Chomsky-Hierarchie
7. Turingmaschinen

Das sollte eine sehr kurze Einführung in die meisten der Rechenmodelle bieten den Menschen zu sprechen.    2 : Ich würde ein gutes Lehrbuch der Informatik empfehlen (In meiner Uni Natürlich, ich‘ m Studium von Sipser der Einführung in die Theorie der Berechnung , die sehr gut in ist meine Meinung). Der andere Ansatz würde wahrscheinlich nur sein, auf Wikipedia zu lesen. Sie können tatsächlich eine Menge Kilometer aus dem Wikipedia-Artikel erhalten, wenn Sie wissen, was Sie in welcher Reihenfolge suchen. Auch, wenn etwas unklar ist, können Sie in der Regel es Google und mehr Ressourcen zu diesem speziellen Thema. Als Ausgangspunkt, würde ich zu den folgenden Themen zu lesen empfehlen (in der aufgeführten Reihenfolge): 1. 1 : http://www.amazon.com/Introduction -Theorie-Computation-Second-Michael / dp / 0534950973 / ref = sr_1_1? ie = UTF8 & s = Bücher & qid = 1263282346 & sr = 8-1

Answer 2

Die Video-Vorlesungen aus folgendem Link gibt gute Einführung in die Theorie der Berechnung. Dies ist eine der besten Ressourcen zu diesem Thema.

Video Vorlesungen über Theorie der Berechnung von Prof. Shai Simonson

Answer 3

Ein älterer Text, der nur schwer zu finden ist Hopcroft und Ullmanns „Einführung in die Automatentheorie, Sprachen, and Computation“. Es gibt eine Reihe von Ausgaben --- Ich habe gehört, dass '79 das Beste ist, in so viel wie es die wenigsten Schläge zieht komplexe Sachen einzuführen. Es ist ein legitimes, wenn auch kleine Lehrbuch, und es führt das ganze Feld, nicht nur, was Sie suchen. Ich schlage vor, dies auf der wahrscheinlich vergeblichen Hoffnung, dass vielleicht einer jener „heikler“ Beweise andere Quellen auslassen kann Ihr Schlüssel sein.

Als sanfter Ausgangspunkt, gibt es ein paar handliche „Benchmark“ Sprachen.

• Wenn Ihr Modell kann die Sprache aller Strings erkennen, wo es die gleiche Anzahl von As und Bs in einer Reihe ist, dann ist es zumindest stärker als FSM.
• Wenn es nicht, dann ist es können zu FSM entsprechen.
• Und falls Ihr Modell kann die Sprache aller Strings erkennen, wo die die gleiche Anzahl von As, Bs und Cs in einem String, dann ist es mehr mächtiger als ein CFG oder PDA.

Diese „Benchmark Sprachen“ sind wirklich nur Funktionen in der Verkleidung --- die ersten im Grunde fragen, ob zwei einstellige Zahlen gleich sind, ist die zweite Frage, ob 3 einstellige Zahlen gleich sind. Sie sind nett und einfach, und sind bekannt oberhalb oder unterhalb der Fähigkeiten von bestimmten Modellen zu sein. Ich weiß nicht, einfach diejenigen für die komplexeren Maschinen, so dass Sie auf eigene Faust sein kann.

Beachten Sie, dass für das Modell „LBA“, linear begrenzt Automaten, glaube ich, dass es keine bekannte natürliche Sprache, die mit einem TM berechenbar ist, aber kein LBA. Diese Aussage wird von verschwommenen Erinnerungen gezogen, so nehmen Sie es nicht als formalen Beweis. :)

Hinweis (schließlich), dass die „Benchmark“ Sprachen etablieren NICHT GLEICHBERECHTIGUNG. Das heißt, wenn Ihr Modell nicht zwei einstellige Zahlen zu vergleichen, das tut nicht bedeutet es zu einer FSM notwendigerweise äquivalent ist, könnte es sein, noch schwächer. Die Sprachen würden nur festzustellen, was sie größer ist als an der Macht, oder weniger als an der Macht.

Auf einer vollständig (ganz) andere Spur, Buch Sipser das tut Beweise Äquivalenz zwischen Regexes und FSM sowie zwischen PDAs und CFG. Ich bin mir nicht sicher, wie nützlich das sein wird, wie Sie ganz vage an, welche Art von Modell der Berechnung Sie in Betracht ziehen, aber wenn Sie tot-Set auf Äquivalenz, diejenigen gut sein können Ausgangspunkte.