Martin Hofmann, Martin Lange's Automatentheorie und Logik PDF

February 14, 2018 | German 1 | By admin | 0 Comments

By Martin Hofmann, Martin Lange

ISBN-10: 3642180892

ISBN-13: 9783642180897

Das Buch beschäftigt sich mit der Theorie endlicher Automaten auf endlichen und unendlichen Wörtern sowie Bäumen. Es behandelt klassische Resultate wie die Sätze von Büchi und Rabin, die zeigen, wie sich monadische Logiken 2. Stufe auf diesen Strukturen mithilfe dieser Automatentheorie entscheiden lassen.

Die einzelnen Kapitel sind in vier Teile zusammengefasst. Diese unterscheiden sich in den Strukturen, über denen jeweils Automatentheorie und Logik betrieben wird. Der erste Teil behandelt endliche Wörter. Der Zweite die Theorie auf den Bereich der Bäume auszudehnen. Der dritte Teil beschäftigt sich kurz mit endlichen Bäumen. Im vierten Teil geht es dann um Automatentheorie und Logik über unendliche Bäume.

Jeder Teil endet mit Vorschlägen für Übungsaufgaben zu dem behandelten Stoff, sowie Notizen, welche auf weiterführende Literatur verweisen oder die Herkunft von präsentierten Resultaten erklären. Das Buch ist an sich ein geschlossenes Werk, welches mit den bereits erwähnten Vorkenntnissen zur Theorie formaler Sprachen und zunächst ohne weitere Hilfsmittel durchgearbeitet werden kann.

Show description

Read Online or Download Automatentheorie und Logik PDF

Best german_1 books

Bernd W. Klöckner's Kompaktwissen Altersvorsorge: Das Produkthandbuch zum PDF

Dieses Buch ist ein Nachschlagewerk für viele in der Praxis wiederkehrende Fragen. Der dargestellte theoretische Hintergrund wird zur foundation für jede Argumentation. Finanzberater können unabhängig von ihrer Firmierung (Makler, Mehrfachagent, Ausschließlichkeitsvertreter) qualifizierte Erstberatungen führen.

Extra resources for Automatentheorie und Logik

Example text

Tn−1 ) Zahlenfolgen mit si < |u|, ti < |v| f¨ ur alle i = 0, . . , n − 1. Das Spiel Gk ((u, s), (v, t)) wird so gespielt wie Gk (u, v) mit der Ausnahme, dass die Verbindungen si —ti bereits als vorhanden gelten, somit d¨ urfen die Positionen si in u und ti in v von Duplicator nicht mehr gespielt werden, es sei denn, Spoiler h¨atte zuvor die korrespondierende Position gespielt. Außerdem d¨ urfen die Verbindungen si —ti nicht gekreuzt werden. B. si < sj und tj < ti ) oder verschiedene Buchstaben verbinden, so hat Duplicator sofort verloren, also schon nach 0 Runden.

Somit hat Spieler P0 in diesem Spiel keine Gewinnstrategie. ⊔ ⊓ 4 Sternfreie Sprachen Wir studieren nunmehr eine echte Teilklasse der regul¨aren Sprachen: die sternfreien Sprachen. Wie die regul¨ aren Sprachen erlauben diese mehrere ¨aquivalente Charakterisierungen: durch sternfreie regul¨are Ausdr¨ ucke beschreibbar, durch erststufige Logik definierbar, etc. 1 Erststufige Logik Die erststufige Logik (FO) ist das Fragment der WMSO, in dem keine Quantifikation u ¨ ber zweitstufige Variablen erlaubt ist.

Sei A = (Q, Σ, q0 , δ, F ) ein NFA. Definiere A′ := (Q⊎{⊥}, Σ, q0 , δ ′ , F ) mit   p , falls q ∈ Q und δ(q, a) = ∅ p∈δ(q,a) δ ′ (q, a) :=  ⊥ , sonst Klar ist, dass A′ nur h¨ ochstens n + 1 Zust¨ ande besitzt. F¨ ur die Korrektheit der Konstruktion argumentieren wir wie folgt. 34 3 Alternierende, endliche Automaten “⊇” Angenommen, w ∈ L(A). Sei also q0 , . . , qn ist ein akzeptierender Lauf von A auf w. Dann ist dies—aufgefasst als Baum mit Wurzel q0 und Blatt qn —auch ein Lauf von A′ auf w.

Download PDF sample

Automatentheorie und Logik by Martin Hofmann, Martin Lange


by David
4.4

Rated 4.47 of 5 – based on 42 votes