Einführung in Berechenbarkeit, formale Sprachen und Komplexitätstheorie

Michael Kortenjan 1

HEINZ NIXDORF INSTITUTUniversität Paderborn

Algorithmen und Komplexität

Wintersemester 2005 / 2006

15.11.05

8. Vorlesung

Michael Kortenjan 2

Turingmaschinen

Michael Kortenjan 3

Algorithmen und KomplexitätTuringmaschinen

Arbeitet auf unbeschränktem Band

Eingabe steht zu Beginn am Anfang des Bands

Auf dem Rest des Bandes steht t (Blank)

Position auf dem Band wird durch Lesekopf beschrieben

Michael Kortenjan 4

Michael Kortenjan 5

Algorithmen und KomplexitätBeispiel einer Turingmaschine

Teste, ob ein Wort in der folgenden Sprache liegt:

L = {w#w | w 2 {0, 1} }

Vorgehensweise:- Von links nach rechts über das Wort laufen- Erstes Zeichen links merken und markieren- Erstes Zeichen rechts von # vergleichen und markieren- Für alle Zeichen wiederholen bis erreicht- Links dürfen dann nur noch Blanks folgen- Falls Zeichen an einer Stelle nicht übereinstimmen

ablehnen, sonst am Ende akzeptieren

Michael Kortenjan 6

Algorithmen und KomplexitätBeispiel einer Turingmaschine

0 1 1 0 0 0 # 0 1 1 0 0 0 t …

x 1 1 0 0 0 # 0 1 1 0 0 0 t …

x 1 1 0 0 0 # x 1 1 0 0 0 t …

x x 1 0 0 0 # x 1 1 0 0 0 t …

x x x x x x # x x x x x x t …accept

Michael Kortenjan 7

Eine (deterministische 1-Band) Turingmaschine (DTM) wird beschrieben durch ein 7-Tupel M = (Q, q0, qaccept, qreject).

Dabei sind Q, endliche, nichtleere Mengen und es gilt: F µ Q, µ , q0 2 Q

t 2 n ist das Blanksymbol.

Q ist die Zustandsmenge, ist das Eingabealphabet, das Bandalphabet.

q0 2 Q ist der Startzustand.qaccept 2 Q ist der akzeptierende Endzustandqreject 2 Q ist der ablehnende Endzustand

: Q £ ! Q £ £ {L, R} ist die (partielle) Übergangsfunktion. Sie ist für kein Argument aus {qaccept, qreject} £ definiert.

Michael Kortenjan 8

Algorithmen und KomplexitätArbeitsweise einer Turingmaschine

Inintial:

- Eingabe steht links auf dem Band

- Der Rest des Bands ist leer

- Kopf befindet sich ganz links

Berechnungen finden entsprechend der Übergangsfunktion statt

Wenn der Kopf sich am linken Ende befindet und nach links bewegen soll, bleibt er an seiner Position

Wenn qaccept oder qreject erreicht wird, ist die Bearbeitung beendet

Michael Kortenjan 9

Algorithmen und KomplexitätKonfiguration

Momentaufnahme einer TM

Bei Bandinschrift uv (dabei beginnt u am linken des Bandes und hinter vstehen nur Blanks),

Zustand q,

Kopf auf erstem Zeichen von v

Konfiguration C = uqv

Michael Kortenjan 10

Algorithmen und KomplexitätAufeinanderfolgende Konfigurationen

Gegeben: Konfigurationen C1, C2

Wir sagen: Konfiguration C1 führt zu C2, falls die TM von C1 in einem Schritt zu C2 übergehen kann.

Formal:

Seien a, b, c 2 , u, v 2 * und Zustände qi , qj gegeben

Wir sagen uaqibv führt zu uqjacv, falls

(qi, b) = (qj , c, L) und

uaqi bv führt zu uacqj v falls (qi , b) = (qj , c, R)

Algorithmen und KomplexitätKonfigurationen

Startkonfiguration: q0w, wobei w die Eingabe ist

Akzeptierende Konfiguration: Konfigurationen mit Zustand qaccept

Ablehnende Konfiguration: Konfigurationen mit Zustand qreject

Haltende Konfiguration: akzeptierende oder ablehnende Konfigurationen

Algorithmen und KomplexitätAkzeptanz von Turingmaschinen

Eine Turingmaschine M akzeptiert eine Eingabe w, falls es eine Folge von Konfigurationen C1, C2, …, Ck gibt, so dass

1. C1 ist die Startkonfiguration von M bei Eingabe w

2. Ci führt zu Ci + 1

3. Ck ist eine akzeptierende Konfiguration

Die von M akzeptierten Worte bilden die von M akzeptierte Sprache L(M)

Eine Turingmaschine entscheidet eine Sprache, wenn jede Eingabe in einer haltende Konfiguration Ck resultiert

Algorithmen und KomplexitätRekursive und rekursiv aufzählbare Sprachen

Eine Sprache L heißt rekursiv aufzählbar, falls es eine Turingmaschine M gibt, die L akzeptiert

Eine Sprache L heißt rekursiv oder entscheidbar, falls es eine Turingmaschine M gibt, die L entscheidet

Algorithmen und KomplexitätBeispiel für eine Turingmaschine

Gesucht: Turingmaschine, die

L = {02n | n ¸ 0}

entscheidet

Arbeitsweise:

1. Gehe von links nach rechts über die Eingabe und ersetze jede zweite 0 durch x

2. Wenn nur eine 0 auf dem Band ist, akzeptiere

3. Falls die Anzahl der 0en ungerade ist, lehne ab

4. Bewege den Kopf zurück an das linke Ende

Algorithmen und KomplexitätBeispiel

Definition der Turingmaschine:

Q = {q1, q2, q3, q4, q5, qaccept, qreject}

= {0, x, t}Startzustand q1

Akzeptierender Endzustand qaccept

Ablehnender Endzustand qreject

Übergangsfunktion

Darstellung von als Diagramm

Darstellung von als Tabelle

q1 (q2, t, R) (qreject, x, R) (qreject, t, R)

q2 (q3, x, R) (q2, x, R) (qaccept, t, R)

q3 (q4, 0, R) (q3, x, R) (q5, t, L)

q4 (q3, x, R) (q4, x, R) (qreject, t, R)

q5 (q5, 0, L) (q5, x, L) (q2, t, R)

Algorithmen und KomplexitätAbarbeitung eines Beispielworts

Beispiel für das

Wort: 0000

Startkonfiguration:

q10000

0 0 0 0 t t

Beispiel für das

Wort: 0000

Konfiguration:

tq2000

t 0 0 0 t t

Beispiel für das

Wort: 0000

Konfiguration:

txq300

t x 0 0 t t

Beispiel für das

Wort: 0000

Konfiguration:

tx0q40

t x 0 0 t t

Beispiel für das

Wort: 0000

Konfiguration:

tx0xq3t

t x 0 x t t

Beispiel für das

Wort: 0000

t x 0 x t t

Beispiel für das

Wort: 0000

t x 0 x t t

Beispiel für das

Wort: 0000

t x 0 x t t

Beispiel für das

Wort: 0000

t x 0 x t t

Beispiel für das

Wort: 0000

t x 0 x t t

Beispiel für das

Wort: 0000

t x 0 x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

t x x x t t

Beispiel für das

Wort: 0000

Endkonfiguration:

txxxtqaccept

t x x x t t

qaccept

Algorithmen und KomplexitätMehrband Turingmaschinen

Eine Mehrband oder k-Band Turingmaschine (k-Band DTM) hat k Bänder mit je einem Kopf.

Die Übergangsfunktion ist dann von der Form: Q £ k ! Q £ k £ {L, R, S }k.

Zu Beginn steht die Eingabe auf Band 1, sonst stehen überall Blanks. Die Arbeitsweise ist analog zu 1-Band-DTMs definiert.

Äquivalenz von 1-Band und Mehrband Turingmaschinen

Satz: Zu jeder Mehrband Turingmaschine gibt es eine äquivalente 1-Band Turingmaschine

Beweis:

Idee: Simuliere Mehrband DTM M auf 1-Band DTM S

Algorithmen und KomplexitätBeweis Fortsetzung

Schreibe k Bänder hintereinander auf ein Band

Sei # zusätzliches Symbol

Verwende # um Bänder zu trennen

Für 2 füge zum Alphabet hinzu

Der Punkt repräsentiert die aktuelle Position des Kopfes auf dem Band

Algorithmen und KomplexitätBeweis Fortsetzung

Bei Eingabe w = w1, … , wn:1. S bildet Startkonfiguration von M ab:

2. Simulation eines Schrittes:Gehe von links nach rechts über das Band und suche die

Markierungen # und finde die Zeichen unter den virtuellen Köpfen

Gehe von links nach rechts über das Band und führe die Änderungen entsprechend der Übergangsfunktion von M durch

3. Falls ein virtueller Kopf rechts auf ein # bewegt wird, schreibe ein t und bewege alle folgenden Zeichen eine Position nach rechts

Äquivalenz von 1-Band und Mehrband Turingmaschinen

Korollar:

Eine Sprache L ist genau dann rekursiv aufzählbar, wenn es eine Mehrband Turingmaschine gibt, die L akzeptiert

Heinz Nixdorf Institut& Institut für InformatikUniversität PaderbornFürstenallee 1133102 Paderborn

Tel.: 0 52 51/60 64 52Fax: 0 52 51/60 64 82E-Mail: mail@upb.dehttp://www.upb.de/cs/ag-madh

Wir danken für Ihre Aufmerksamkeit!Wir danken für Ihre Aufmerksamkeit!

Einführung in Berechenbarkeit, formale Sprachen und Komplexitätstheorie

Documents

Berechenbarkeit und Formale Sprachen · Eine Kon guration Kist ein Element aus Q . TM Mist in Kon guration K= q \ ,Auf dem Band steht und der Kopf steht unter dem ersten Zeichen von

Komplexitätstheorie - uni-luebeck.de · 2020. 7. 17. · 2 TeilI Einführung TeilI Einführung Vorlesungen zur Komplexitätstheorie leiden daran, dass sie anfangs immer recht langweilig

Formale Sprachen Teil 2

Friedhelm Meyer auf der Heide 1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit und Formale Sprachen

Angewandte Komplexitätstheorie - leuphana.de · 1.1 Angewandte Komplexitätstheorie 1 Fachhochschule Nordostniedersachsen Fachbereich Wirtschaft Prof. Dr. Ulrich Hoffmann November

Formale Rahmenwerke - univie.ac.at

Komplexitätstheorie WiSe 2011/12 in Trier · Komplexitätstheorie WiSe 2011/12 in Trier Henning Fernau Universität Trier fernau@uni-trier.de 1

Praktische Grenzen der Berechenbarkeit

Modulhandbuch - uni-wuerzburg.de · Graphentheoretische Konzepte und Algorithmen 27 Komplexitätstheorie 28 Objektorientiertes Programmieren 29 Rechnerarchitektur 30 Rechnernetze

Tutorium zu Berechenbarkeit und Komplexit at

F3 – Berechenbarkeit und Komplexität€¦ · FormaleGrundlagenderInformatik,F3–BerechenbarkeitundKomplexität –15– 1.3Algorithmus DieSummedererstennnatürlichenZahlenist

Automaten, formale Sprachen und Berechenbarkeit 1home.in.tum.de/~hauffa/fsab-skript.pdf · 1 0. Einleitung Automaten und formale Sprachen sind Teilgebiete der theoretischen Informatik:

Grenzen der Berechenbarkeit Inhaltsverzeichnis · Moderne Kryptographie Grenzen der Berechenbarkeit Ausblick in die Kryptographie Moderne Kryptographie Ver- und Entschlüsselungsvorgang

Berechenbarkeit Klaus Becker 2014. 2 Berechenbarkeit

Formale Systeme II: Theorie

1 HEINZ NIXDORF INSTITUT Universität Paderborn Algorithmen und Komplexität Einführung in Berechenbarkeit, Formale Sprachen und Komplexitätstheorie Wintersemester

Skript zur Vorlesung ” Formale Sprachen und Berechenbarkeit“

Automaten, formale Sprachen und Berechenbarkeit II SoSe 2004 Prof. W. Brauer Teil 1: Wiederholung (Vor allem Folien von Priv.-Doz. Dr. Kindler vom WS 2001/02

Chaos- und Komplexitätstheorie

Beate M.W. Ratter – Mainz – Hamburg Überraschung und Unsicherheit – Schlüsselbegriffe der Komplexitätstheorie und ihr Beitrag zur Katastrophenforschung