Formale Sprachen und Automaten
Jan Hladik
DHBW Stuttgart
Sommersemester 2019
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 1 / 160
Inhalt
Turing-MaschinenMotivationTuring-MaschinenMehrband-TuringmaschinenUnbeschränkte GrammatikenLinear Beschränkte Automaten
EntscheidbarkeitBerechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 2 / 160
Inhalt
Turing-MaschinenMotivationTuring-MaschinenMehrband-TuringmaschinenUnbeschränkte GrammatikenLinear Beschränkte Automaten
EntscheidbarkeitBerechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 3 / 160
Ziele
Formale Sprachen Maschinenmodelle für Sprachen von Typ 1 und 0AbschlusseigenschaftenEntscheidungsprobleme
Algorithmik Präzise Definition von „Algorithmus“Berechenbarkeit und EntscheidbarkeitGrenzen von Algorithmen / Computern
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 4 / 160
Wozu Turing-Maschinen und Berechenbarkeit?Turing-Maschinen
komplexer als bisherige Berechnungsmodelle (EA, KA)gleich mächtig wie Computernur rudimentäre Funktionen
Nachteil: umständlich in der AnwendungVorteil: ermöglicht Beweise
(Scott Adams hat Wirtschaftswissenschaften und Management studiert...)
Es ist möglich, zu beweisen, dass eine TM (Computer) etwas nicht kann!Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 5 / 160
Inhalt
Turing-MaschinenMotivationTuring-MaschinenMehrband-TuringmaschinenUnbeschränkte GrammatikenLinear Beschränkte Automaten
EntscheidbarkeitBerechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 6 / 160
Turing-Maschinen und formale Sprachen
Vier Sprachklassen definiert durch Grammatiken und Maschinenmodelle:
Typ Sprachklasse Maschinenmodell0 rekursiv aufzählbar ?1 kontextsensitiv ?2 kontextfrei Kellerautomat3 regulär endlicher Automat
Type 0 (?)
Type 1 (?)
Type 2 (PDA)
Type 3 (DFA/NFA)
(all languages)
Nötig ist mächtigeres Modell als Kellerautomat
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 7 / 160
Geschichte
1936 von Alan Turing vorgestelltPaper: On computable numbers, with anapplication to the Entscheidungsproblemverwendet TM für Beweis der Unentscheidbarkeitdes Erfüllbarkeitsproblems der Prädikatenlogik
Modell eines universellen Computerssehr einfach aufgebaut (und damit leicht zuhandhaben)aber genauso mächtig wie jede vorstellbareMaschine
Alan M. Turing(1912–1954)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 8 / 160
Konzept
t a p e# #
Medium: unendliches Band (bidirektional)enthält anfangs Eingabe (und Blanks #)dient auch für Ausgabe undZwischenergebnissekann gelesen und beschrieben werdenLesekopf kann beliebig bewegt werden
ÜbergängeLesen und Schreiben auf aktuellerBandpositionBewegen des Schreib-/Lesekopfs (`, r ,n)
AkzeptanzbedingungTM ist in Endzustandkeine weitere Bewegung möglich
Gemeinsamkeiten mit EAKontrolleinheit (endliche Zustandsmenge),Start- und EndzuständeEingabealphabet
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 9 / 160
Formale Definition
Definition 1.1 (Turing-Maschine)Eine Turing-Maschine (TM) ist ein 6-Tupel (Q,Σ,Γ,∆, q0,F), wobei
Q,Σ, q0,F wie bei EAs definiert sind;Γ ⊇ Σ ∪ {#} das Band-Alphabet istund zumindest Σ und das Blank-Symbol enthält;∆ ⊆ Q × Γ× Γ× {`,n, r} ×Q die Übergangsrelation ist.
Wenn ∆ höchsten einen Übergang (p, a, b, d, q) für jedes Paar(p, a) ∈ Q × Σ enthält, heißt die TM deterministisch (DTM). DieÜbergangs-Funktion wird dann mit δ bezeichnet.
Γ kann weitere Zeichen enthaltenDas macht die TM nicht mächtiger, aber leichter handhabbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 10 / 160
Übergänge
∆ ⊆ Q × Γ× Γ× {`,n, r} ×Q
TM ist in Ausgangszustandliest Bandsymbol an aktueller Positionschreibt Bandsymbol auf aktuelle Positionbewegt Kopf nach links, rechts oder gar nichtgeht in Folgezustand
Übergang (p, a, b, `, q) kann auch geschrieben werden als
p a → b ` q
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 11 / 160
Beispiel: Übergang
Beispiel 1.2 (Übergang 1, t → c, r , 2)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 12 / 160
Konfigurationen
Definition 1.3 (Konfiguration)Eine Konfiguration c = αqβ einer Turing-MaschineM = (Q,Σ,Γ,∆, q0,F) besteht aus
dem aktuellen Zustand q ∈ Q;dem Band-Inhalt α ∈ Γ∗ links von der aktuellen Kopf-Position(ohne unendliche #-Folgen)dem Bandinhalt β ∈ Γ∗ beginnend mit der aktuellen Kopf-Position(ohne unendliche #-Folgen)
Eine Konfiguration c = αqβ heißt akzeptierend, wenn q ∈ F gilt.
Eine Konfiguration c heißt Stop-Konfiguration, wenn es keine Übergängevon c aus gibt.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 13 / 160
Beispiel: Konfigurationen
Diese TM ist in der Konfigurationc2ape.
Die Konfiguration 4tape istakzeptierend.Wenn es keine Übergänge der Art4, t → . . . gibt, ist 4tape außerdem eineStop-Konfiguration.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 14 / 160
Folge-Konfiguration
Definition 1.4 (Folge-Konfiguration)Sei
M = (Q,Σ,Γ,∆, q0,F) eine TM undc = vdpaw eine Konfiguration vonM mitp ∈ Q, {a, b, d} ⊆ Γ, {v,w} ⊆ Γ∗.
Die Konfiguration c′ heißt Folgekonfiguration von c (c ` c′), wennc′ = vqdbw gilt für einen Übergang (p, a, b, `, q) ∈ ∆,c′ = vdqbw gilt für einen Übergang (p, a, b,n, q) ∈ ∆, oderc′ = vdbqw gilt für einen Übergang (p, a, b, r , q) ∈ ∆.
Für eine beliebig lange Folge von Übergängen schreibt man auch c `∗ c′.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 15 / 160
Berechnungen
Definition 1.5 (Berechnung, Akzeptanz)Eine Berechnung einer TMM = (Q,Σ,Γ,∆, q0,F) auf einem Wort w isteine Folge von Konfigurationen vonM, die mit q0w beginnt und für diegilt, dass jede weitere Konfiguration eine Folgekonfiguration der vorherigenist.
M akzeptiert w, wenn es eine Berechnung vonM auf w gibt, die miteiner akzeptierenden Stopkonfiguration ca endet, d.h. q0w `∗ ca.
M verwirft w, wenn jede Berechnung vonM auf w in einer nichtakzeptierenden Stopkonfiguration endet.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 16 / 160
Übung: Turing-Maschine für reguläre Sprache
Sei Σ = {a, b} und L = {w ∈ Σ∗ | |w|a ist gerade}.
1 Geben Sie eine TMM an, die L akzeptiert.2 Geben Sie Berechnungen vonM auf den Wörtern abbab und bbab an.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 17 / 160
Eine Turing-Maschine für eine kontextsensitive Sprache
Beispiel 1.6 (TM für anbncn)Mabc = (Q,Σ,Γ,∆, start, {f}) mit
Q = {start, findb, findc, check, back, end, f}
Σ = {a, b, c} und Γ = Σ ∪ {#, x, y, z}
∆start # # n fstart a x r findbfindb a a r findbfindb y y r findbfindb b y r findcfindc b b r findcfindc z z r findcfindc c z r checkcheck c c ` backcheck # # ` end
∆back z z ` backback b b ` backback y y ` backback a a ` backback x x r startend z z ` endend y y ` endend x x ` endend # # r f
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 18 / 160
Übung: Turing-Maschinen für kontextsensitive Sprachen
1 Geben Sie Berechnungen vonMabc auf den Wörtern aabbcc und aabcan.
2 Wie viele Schritte brauchtMabc in Abhängigkeit von der Länge derEingabe (O-Notation)?
3 Entwickeln Sie ein Turing-MaschineMW , die die SpracheLW = {wcw | w ∈ {a, b}∗} akzeptiert.
4 Wie viele Schritte braucht Ihre TM in Abhängigkeit von der Länge derEingabe?
5 Überlegen Sie, wie SieMW modifizieren müssen, um Wörter derForm ww zu akzeptieren.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 19 / 160
Inhalt
Turing-MaschinenMotivationTuring-MaschinenMehrband-TuringmaschinenUnbeschränkte GrammatikenLinear Beschränkte Automaten
EntscheidbarkeitBerechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 20 / 160
Praktische Probleme
Vorteil TM gegenüber Kellerautomat: Unbegrenztes Bandbeliebig lange ZwischenergebnisseZeichen können beliebig oft gelesen werden.
Praktischer Nachteil: Eingabe und Zwischenergebnisse hintereinander aufdemselben Band
Umständliches Hin-und-her-Spulen des BandesVerlängern eines Teils erfordert Verschieben des komplettenRestinhalts
Abhilfe: TM mit mehreren Bändernz.B. ein Band Ein-/Ausgabe, ein Band ZwischenergebnisseKöpfe können unabhängig über Bänder bewegt werden
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 21 / 160
Mehrband-Turingmaschinen
Definition 1.7 (k-Band-Turing-Maschine)Eine k-Band-TM ist ein 6-Tupel (Q,Σ,Γ,∆, q0,F), wobei
Q, Σ, Γ, q0 und F definiert sind wie für (Einband-)TM und∆ ⊆ Q × Γk × Γk × {r , `,n}k ×Q gilt.
Beispiel 1.8 (Übergang (p, (a, a, c), (b, c, c), (`, r , n), q))
Wenn die TM im Zustand p istund auf den Bändern 1–3 die Symbole a, a und c stehen,werden diese mit b, c bzw. c überschrieben,die 3 Köpfe bewegen sich nach links, rechts bzw. gar nicht,anschließend geht die Maschine in den Zustand q über.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 22 / 160
Konfiguration einer Mehrband-TM
Definition 1.9 (Konfiguration)Eine Konfiguration c = αqβ einer Mehrband-TM ist definiert wie die einerEinband-TM, mit dem Unterschied, dass α und β Elemente von (Γk)∗ sind.Berechnung und Akzeptanz sind definiert wie für Einband-TM.
Beispiel 1.10 (Konfiguration 3-Band-TM)
a#c
b
##
c
b#
d
bc
q5
c#a
#
c#
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 23 / 160
Beispiel: 2-Band-TM für anbncn
Beispiel 1.11 (TM für anbncn)
M2 = (Q,Σ,Γ,∆, start, {f}) mit
Q = {start, reada, readb, readc, f}
Σ = {a, b, c}
Γ = Σ ∪ {#}
∆ siehe Tabelle
Vorteile:
nur O(|w|) Schritte
einfachere Übergangsrelation
keine zusätzlichen Band-Symbole
kein Abschluss-Check
start(
##
) (##
) (nn
)f
start(
a#
) (aa
) (rr
)reada
reada(
a#
) (aa
) (rr
)reada
reada(
b#
) (b#
) (n`
)readb
readb(
ba
) (bb
) (r`
)readb
readb(
c#
) (c#
) (nr
)readc
readc(
cb
) (cc
) (rr
)readc
readc(
##
) (##
) (nn
)f
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 24 / 160
Übung: 2-Band-TM
1 Geben Sie die Berechnungen vonM2 auf den Wörtern aabbcc undaabc an.
2 Geben Sie eine 2-Band-TM für die Sprache {ww | w ∈ {a, b}∗} an, diefür eine Eingabe der Länge n nur O(n) Berechnungsschritte benötigt.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 25 / 160
Simulation durch 1-Band-TM
Die 1-Band-TMM1 simuliert k-Band-TMMk = (Q,Σ,Γ,∆, q0,F)statt k Bänder: ein Band mit k Spuren ; Alphabet Γk
Kopfpositionen: weitere k Spuren: X markiert Kopfposition, sonst #Berechnungsschritte:
laufe über verwendetes Band (Anfangs-/ End-Markierungen)merke Inhalt von Spur i, wenn auf Spur k + i ein X stehtfinde passenden Übergang in ∆modifiziere Spursymbole und Kopfpositionen
Anmerkungexplizite Darstellung vonM1 sehr umfangreich
umständlich aufzuschreibenschwer zu verstehen
für komplexe Konstruktionen: informelle Beschreibung einer TMeinzelne Schritte offensichtlich mit TM machbar
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 26 / 160
Äquivalenz von 1-Band- und k-Band-TM
Satz 1.12Jede Sprache, die von einer k-Band-Turingmaschine erkannt wird, wirdauch von einer (1-Band-)Turing-Maschine erkannt.Die Maschinenmodelle „Turing-Maschine“ und „k-Band-Turing-Maschine“sind äquivalent.
Wichtig
Zustandsmenge wird sehr großΓk Zustände zum Merken des Bandinhalts
viel mehr Berechnungsschritte nötigfunktioniert nur für festes k!
Merken in Zuständen sonst nicht möglich
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 27 / 160
Determinismus
Definition 1.13 (Deterministische Turing-Maschine)Eine deterministische Turing-Maschine (DTM) ist eine TM(Q,Σ,Γ,∆, q0,F), deren Übergangsrelation ∆ für jedes Paar q ∈ Q,c ∈ Γ höchstens einen Übergang (q, c, c′,m, q ′) enthält.
Existenz eines Übergangs ist nicht gefordertsonst gäbe es keine Stopkonfigurationen
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 28 / 160
Simulation von NTM durch DTM
NTM A akzeptiert w, wenn eine Berechnung existiert, die zu einerakzeptierenden Stopkonfiguration führt.
Satz 1.14 (Äquivalenz von DTM und NTM)Jede NTM A = (Q,Σ,Γ,∆, q0,F) kann durch eine DTM Adet simuliertwerden.DTMs und NTMs beschreiben dieselbe Sprachklasse.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 29 / 160
Funktionsweise von Adet
Beweis.Verwende 2-Band-DTM für Adet:
Band 1: Aufzählung aller möglichen Konfigurationen von A auf wfunktioniert als Warteschlange (queue)beginnend mit q0wzusätzliche Bandsymbole: qi Zustände, „*“ als Trennsymbol,„!“ für aktuelle Konfiguration ca
Band 2: Zwischenspeicher für KonfigurationenAblauf:
1 wenn ca akzeptierende Stopkonfiguration ist, gehe in akz. SK2 sonst kopiere ca auf B2; gehe ans Ende von B13 für k mögliche Übergänge von ca: erzeuge k Kopien von ca auf B1
(getrennt durch „*“)4 modifiziere Kopien auf B1 entsprechend ∆5 bewege Marker „!“ eine Konfiguration nach rechts6 weiter bei 1
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 30 / 160
Inhalt
Turing-MaschinenMotivationTuring-MaschinenMehrband-TuringmaschinenUnbeschränkte GrammatikenLinear Beschränkte Automaten
EntscheidbarkeitBerechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 31 / 160
Turing-Maschinen und unbeschränkte Grammatiken
Satz 1.15 (Äquivalenz von Turing-Maschinen undTyp-0-Grammatiken)Die Klasse der von Turing-Maschinen erkennbaren Sprachen ist die Klasseder Sprachen, die durch unbeschränkte Grammatiken erzeugt werden
Beweis.
1 Simuliere Grammatik-Ableitungen mit TM2 Simuliere Berechnung einer TM mit Grammatik
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 32 / 160
Simulation einer Typ-0-Grammatik mit TM
Gegeben: Grammatik G = (N ,Σ,P,S)Verwende nicht-deterministische 2-Band-TM:
Band 1 speichert Eingabewort wBand 2 simuliert von S ausgehende Ableitungen gemäß PAblauf:
1 wähle (nicht-deterministisch) Position p auf B22 wenn das auf p beginnende Wort zu einer Regel α→ β passt
verschiebe Bandinhalt wenn nötigersetze α durch β
3 vergleiche B2 mit B1wenn gleicher Inhalt, gehe in akzeptierende Stopkonfigurationsonst weiter bei 1
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 33 / 160
Simulation einer TM mit Typ-0-Grammatik
Ziel: Transformation von TM A in Grammatik GATechnische Schwierigkeit:
Berechnung von A:1 A erhält Eingabewort w am Anfang;2 A kann w lesen und verändern;3 A akzeptiert oder nicht (Stopkonfiguration oder Endlosschleife).
Ableitung von GA:1 GA beginnt mit S ;2 GA wendet Regeln auf Teilwörter an;3 GA erzeugt möglicherweise Terminalwort w am Ende.
Zur Simulation der Berechnung von A muss GA1 ein Terminalwort w erzeugen;2 die Berechnungsschritte von A simulieren;3 w wiederherstellen, falls die Berechnung akzeptierend ist.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 34 / 160
Regeln von GASei A = (Q,Σ,Γ,∆, q0,F). GA hat drei Gruppen von Regeln:
1 Erzeugen eines beliebigen w ∈ Σ∗ mit Blanks und Startzustand; Startkonfiguration # . . .#q0input# . . .#
2 Simulation der Berechnung von A auf w(p, a, b, r , q) ; pa → bq(p, a, b, `, q) ; cpa → qcb (für alle c ∈ Γ)(p, a, b,n, q) ; pa → qb
3 Wiederherstellung des Ausgangsworts w nach Erreichen vonakzeptierender Stopkonfiguration
benötigt komplexeres Alphabet mit „Backup-Spur“
Startkonfiguration: · · ·(
##
)(q0q0
)(ii
)(nn
)(pp
)(uu
)(tt
)(##
)· · ·
Simulation der Berechnung nur in erster Komponente
; · · ·(
a#
)(iq0
)(di
)(#n
)(ap
)(#u
)(qft
)(d#
)· · ·
Wiederherstellung von w aus zweiter Komponente: ; inputJan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 35 / 160
Übung: Simulation von TM durch GrammatikGegeben sei die TMM = ({0, 1, 2, 3, 4}, {a}, {a,#},∆, 0, {4}) mit ∆ inder folgenden Tabelle:
0 a # r 10 # # n 41 a a r 11 # # ` 22 a # ` 33 a a ` 33 # # r 0
1 Geben Sie Regeln für die Gruppen 1 und 2 des beschriebenenVerfahrens an, um eine Grammatik GM zu erzeugen, die dieBerechnung vonM simuliert (ohne Backup-Spur).
2 Geben Sie eine Ableitung von GM an, die die Berechnung von A aufdem Wort aaaa simuliert (ohne Wiederherstellung desEingabewortes).
3 Welche Sprache erkenntM?Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 36 / 160
Inhalt
Turing-MaschinenMotivationTuring-MaschinenMehrband-TuringmaschinenUnbeschränkte GrammatikenLinear Beschränkte Automaten
EntscheidbarkeitBerechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 37 / 160
Linear Beschränkte Automaten
Kontextsensitive Grammatiken: Keine kürzenden RegelnLBA: Nur Platz für Eingabewort w
Marker kennzeichnen Grenzen von wSchreib-/Lesekopf darf Marker nicht passieren oder überschreiben
. . . > i n p u t < . . .
Definition 1.16 (LBA)Ein linear beschränkter Automat ist eine Turing-MaschineM = (Q,Σ,Γ,∆, q0,F) so dass
{>,<} ⊂ Γ \ Σ gilt undÜbergänge mit Markern nur in der Form (q, >, > , r , q ′) und(q, <, < , `, q ′) in ∆ enthalten sind.
Die von A akzeptierte Sprache ist die Menge aller Wörter w ∈ Σ∗, für dievon der Startkonfiguration > q0w < aus eine akzeptierendeStopkonfiguration erreicht wird.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 38 / 160
Äquivalenz von ks. Grammatiken und LBAs
Transformation ks. Grammatik G ; LBA AG :wie für Typ-0-Grammatik: verwende 2-Band-TM
speichere Eingabewort w auf Band 1simuliere Operationen von G auf Band 2akzeptiere, wenn Inhalte gleich sind
Da G keine kürzenden Regeln enthält, müssen keine Wörter erzeugtwerden, die länger sind als w
Transformation LBA A ; ks. Grammatik GA:ähnlich wie für TM:
erzeuge zufälliges Eingabewort w ohne Blankssimuliere Berechnung von A auf w
keine kürzenden Regeln vorhanden
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 39 / 160
Abschlusseigenschaften: Reguläre Operationen
Satz 1.17 (Abschluss unter ∪, ·,∗)Die Klasse der kontextsensitiven Sprachen ist abgeschlossen unter ∪, ·,∗.
Kontext beeinflusst Regelanwendung; Konkatenation und Kleene-Stern aufwändiger als für kf. Grammatiken
Beispiel 1.18
L1 = {anbn | n ∈ N≥1} mit P1 = {S1 → aS1b|ab}L2 = {bn | n ∈ N≥1} mit P2 = {S2 → S2b|b, bS2 → aS2}Konstruktion für analog zu KFG: P = {S → S1S2} ∪ P1 ∪ P2
Ableitung: S ⇒ S1S2 ⇒2 aabbS2 ⇒ aabaS2 ⇒ aabab /∈ L1 · L2
Abhilfe:ersetze TS durch NTS (wie bei CNF) ; Xa,Xb, . . .
benenne NTS disjunkt um ; Xa1 ,Xa2 , . . .
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 40 / 160
Algorithmen für reguläre Operationen
Beweis.Gegeben: KSG G1 = (N1,Σ,P1,S1); G2 = (N2,Σ,P2,S2)L(G1) ∪ L(G2) Wie für KFG:
benenne NTS disjunkt umP = {S → S1,S → S2} ∪ P1 ∪ P2
L(G1) · L(G2) führe für c ∈ Σ neue NTS Xc und Regeln Xc → c einersetze c auf rechten Regelseiten durch Xcbenenne NTS der Grammatiken disjunkt umalle Regeln haben Form N → a oderN1 . . .Nk → M1 . . .MjP = {S → S1S2} ∪ P1 ∪ P2
(L(G1))∗ erzeuge Kopie G ′1 von G1behandle G1 und G ′1 wie bei KonkatenationP = {S → ε|S0,S0 → S1|S1S ′1|S1S ′1S0} ∪ P1 ∪ P ′1
Fallunterscheidungen für ε ∈ L(G1) oder ε ∈ L(G2)Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 41 / 160
Übung: Abschluss unter Kleene-SternGegeben sei die Grammatik G1 = (N ,Σ,P,S) mitL(G1) = {anbncn | n ≥ 1}
N = {S ,B,C},Σ = {a, b, c},P: S → aSBC 1
S → aBC 2CB → BC 3aB → ab 4bB → bb 5bC → bc 6cC → cc 7
1 Verwenden Sie den gezeigten Algorithmus, um eine Grammatik G fürdie Sprache {(anbncn)∗} zu erzeugen.
2 Geben Sie in G eine Ableitung für das Wort aabbccabc an.Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 42 / 160
Abschlusseigenschaften: Durchschnitt
Satz 1.19 (Abschluss unter ∩)Die Klasse der kontextsensitiven Sprachen ist abgeschlossen unterDurchschnitt.
Beweis.
Verwende 2-Band-LBA.Simuliere Berechnung von A1 auf Band 1Simuliere Berechnung von A2 auf Band 2.Akzeptiere, wenn sowohl A1 als auch A2 akzeptieren.
Wenn eine der beiden Simulationen nicht terminiert, terminiert auch dieSimulation nicht, d.h. die Eingabe wird nicht akzeptiert.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 43 / 160
Abschlusseigenschaften: Komplement
Satz 1.20 (Immerman, Szelepcsenyi 1988)Die Klasse der kontextsensitiven Sprachen ist abgeschlossen unterKomplement.
Schwierigkeit: Berücksichtigung (evtl. exponentiell vielen)nichtdeterministischen Ableitungen mit linearem PlatzAnsatz: Speichere nicht alle Ableitungen, sondern nur ihre Anzahl
Beweis.Gegeben: LBA A = (Q,Σ,Γ,∆, q0,F); Wort w ∈ Σ∗Nichtdeterministischer Algorithmus mit linearem Platzbedarf, derakzeptiert gdw. w /∈ L(A):
1 Zähle a: alle möglichen Konfigurationen von A mit Eingabe w2 Zähle b: alle verwerfenden Konfigurationen von A mit Eingabe w3 Wenn a = b: akzeptiere; sonst: verwerfe
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 44 / 160
Entscheidungsprobleme
Satz 1.21 (Wortproblem für ks. Sprachen)Das Wortproblem für ks. Sprachen ist entscheidbar.
Beweis.
N , Σ und P sind endlich.Regeln von P sind nicht-kürzend.Nur endliche Anzahl von Ableitungen möglich für Wort der Länge n.
Algorithmus ist nicht auf linearen Platz beschränktBeweis ist einfacher als für Abgeschlossenheit unter Komplement
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 45 / 160
Entscheidungsprobleme
Satz 1.22 (Leerheitsproblem für ks. Sprachen)Das Leerheitsproblem für ks. Sprachen ist unentscheidbar.
Beweis.Folgt aus Unentscheidbarkeit des Postschen Korrespondenzproblems(nächstes Kapitel).
Satz 1.23 (Äquivalenzproblem für ks. Sprachen)Das Äquivalenzproblem für ks. Sprachen ist unentscheidbar.
Beweis.Wäre das Äquivalenzproblem für ks. Sprachen entscheidbar, dann auch fürkf. Sprachen (da jede kf. Sprache auch ks. ist).
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 46 / 160
Zusammenfassung: Turingmaschine
Turingmaschine: Endlicher Automat plus unendliches Bandlesen und schreibenbeliebige Bewegungen
Unterschiedliche Varianten:Mehrband-TMdeterministische TMdeterministische Einband-TM kann nichtdeterministische undMehrband-TM simulieren
äquivalent zu unbeschränkten GrammatikenLinear beschränkter Automat
Bandlänge beschränkt auf Eingabeäquivalent zu kontextsensitiven Grammatikenabgeschlossen unter allen (betrachteten) Operationennur Wortproblem entscheidbar
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 47 / 160
Inhalt
Turing-MaschinenEntscheidbarkeit
Unentscheidbarkeit, Diagonalisierung und das WortproblemReduktionsbeweiseDas PKP und andere unentscheidbare ProblemeSemi-EntscheidbarkeitDie universelle Turing-MaschineAbschlusseigenschaften
Berechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 48 / 160
Entscheidbarkeit
Bisher: Informelle Vorstellung „Es gibt einen Algorithmus“Abfolge einzelner Schritteeindeutig verständlichjeder Schritt „offensichtlich“ machbar
Jetzt: Formale Definition mit Hilfe von TM
Definition 2.1 (Entscheidbarkeit)Eine Menge S heißt entscheidbar, wenn eine deterministischeTuring-MaschineM existiert, die eine Eingabe w
akzeptiert, wenn w ∈ S gilt,verwirft, wenn w /∈ S gilt.
akzeptiert: Berechnung führt zu akzeptierender Stopkonfigurationverwirft: Berechnung führt zu nicht akzeptierender StopkonfigurationS wird oft als Problem bezeichnet
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 49 / 160
Entscheidbarkeit und Erkennbarkeit
erkennbar es gibt NTM mitw ∈ L eine Berechnung führt zu akzeptierender
Stopkonfigurationw /∈ L jede Berechnung führt zu nicht akzeptierender
Stopkonfiguration oder Endlosschleifeentscheidbar es gibt DTM mit
w ∈ L die Berechnung führt zu akzeptierenderStopkonfiguration
w /∈ L die Berechnung führt zu nicht akzeptierenderStopkonfiguration
Entscheidbar: TM muss immer terminierenEntscheidbare Sprachen sind erkennbar, aber nicht umgekehrtErkennbare Sprachen sind semi-entscheidbar (später)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 50 / 160
Beispiele: Entscheidbarkeit
Beispiel 2.2 (Sabc = {anbncn | n ∈ N})Die Menge Sabc ist entscheidbar, denn es gibt den LBAMabc mitL(Mabc) = Sabc.
Beispiel 2.3 (SP = {ap | p ist prim})Die Menge SP ist entscheidbar.Eine 3-Band-DTM kann wie folgt vorgehen:
Band 1 enthält Eingabe wBand 2 zählt mögliche Teiler t auf(1 < t ≤ w)Band 3 zählt Vielfache v von t auf(t < v ≤ w)
Notation: bi steht für Inhalt von Band i
1 Wenn |b1| < 2: verwerfe2 Schreibe auf Band 2 ein a
3 Hänge an Band 2 ein a an4 Wenn |b1| = |b2|: akzeptiere5 Kopiere Band 2 auf Band 3
6 Hänge b2 an b3 an7 Wenn |b1| = |b3|: verwerfe8 Wenn |b1| < |b3|: weiter bei 39 Weiter bei 6
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 51 / 160
Übung: Turing-Maschine für SP
Der Vergleich von b1 mit b2 oder b3 kann wie beiMabc durchgeführtwerden. Es fehlt eine Methode zum Anhängen eines Bandinhalts an einenanderen Bandinhalt.
Schreiben Sie eine 2-Band-Turing-Maschine mit Alphabet {a}, dieden Anfang von b1 sucht,das Ende von b2 sucht,b1 an b2 anhängt.
Sie können davon ausgehen, dass die Bänder jeweils nur ein Wortenthalten, und dass der jeweilige Schreib-/Lesekopf zu Anfang innerhalbdes Wortes steht.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 52 / 160
Entscheidbarkeit und Komplement
Satz 2.4 (Entscheidbarkeit des Komplements)Sei Σ ein Alphabet und L ⊆ Σ∗ eine Sprache.Ist L entscheidbar, so auch das Komplement L = Σ∗ \ L.
Beweis.SeiM = (Q,Σ,Γ, δ, q0,F) eine DTM, die L entscheidet. Wir definierenM als (Q,Σ,Γ,∆, q0,Q \ F).M entscheidet L, denn
M ist deterministisch;M hält auf jeder Eingabe;M akzeptiert genau die Wörter, die M verwirft.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 53 / 160
Inhalt
Turing-MaschinenEntscheidbarkeit
Unentscheidbarkeit, Diagonalisierung und das WortproblemReduktionsbeweiseDas PKP und andere unentscheidbare ProblemeSemi-EntscheidbarkeitDie universelle Turing-MaschineAbschlusseigenschaften
Berechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 54 / 160
Unentscheidbarkeit
Wie kann Unentscheidbarkeit eines Problems P gezeigt werden?ohne formalen Algorithmen-Begriff
gar nichtAsok: „It’s not logically possible to prove something can’t be done.“
mit Turing-Maschine:Schwierigkeit ähnlich wie bei Pumping-LemmaZeige für unendlich viele TM A, dass A P nicht entscheidetindirekter Beweis: Annahme „A entscheidet P“ führt zu WiderspruchDan: „It’s impossible for most people, but I’m a trained scientist.“
Nachweis der Existenz unentscheidbarer Probleme:1 Codierung von Turingmaschinen2 Definition des speziellen Wortproblems3 Nachweis der Unentscheidbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 55 / 160
Codierung einer TM
Turing-Maschinen können als Eingabe für eine TMM codiert werdenSchwierigkeit:
M hat fixes Alphabet und fixe ZustandsmengeM muss als Eingabe beliebig große Alphabete und Zustandsmengenverarbeiten können
Ziel:M simuliert die Berechnungen beliebiger TM (später)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 56 / 160
Gödelisierung
Gödelisierung mit Alphabet {a, b}:
Zustände {q1, q2, q3, . . .}: a, aa, aaa, . . .Alphabet {s1, s2, s3, . . .}: a, aa, aaa, . . .Kopfbewegung {`,n, r}: a, aa, aaa
Kurt Gödel(1906–1978)
Beispiel 2.5 (Codierung einer TM)
Übergang (q3, s1, s3, r , q1) 7→ aaababaaabaaabaEndzustandsmenge {q1, q2, q4} 7→ abaabaaaa
Konfiguration s2s4q3s1s3 7→ aabaaaabaaabbabaaa
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 57 / 160
Spezielles Wortproblem
Definition 2.6 (Spezielles Wortproblem)Sei T die Menge aller Codierungen von Turing-Maschinen undMw fürw ∈ T die TM mit Codierung w.
Das spezielle Wortproblem W ist die Menge aller Codierungen vonTuring-Maschinen, die ihre eigene Codierung akzeptieren:
W = {w | w ∈ L(Mw)}
Aus dem Satz zur Entscheidbarkeit des Komplements folgt:Ist W entscheidbar, dann auch W = {w | w /∈ L(Mw)}
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 58 / 160
Unentscheidbarkeit des speziellen Wortproblems
Satz 2.7 (Unentscheidbarkeit des speziellen Wortproblems)Das spezielle Wortproblem ist unentscheidbar.
Beweis.Wir zeigen indirekt die Unentscheidbarkeit von W :Angenommen, es gibt eine TMMW , die W entscheidet, und die dieCodierung wW hat. Dann gilt:
wW ∈ L(MW ) gdw MW akzeptiert wW gdw wW /∈ L(MW )
Widerspruch.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 59 / 160
DiagonalisierungSchwierigkeit des Beweises:Zeige für alle unendlich vielen Turing-Maschinen, dass sie das spezielle WPnicht entscheiden.
TM Eing
abe
c(A
)
c(B
)
c(C)
c(D
)
c(E)
. . .A 7
B 7
C 7
D 7
E 7... . . .
Diagonale: TM mit eigener Codierung als Eingabe ; WiderspruchJan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 60 / 160
Weitere Diagonalisierungs-Argumente
Satz 2.8 (Cantor-Diagonalisierung, 1891)Die Menge der reellen Zahlen ist nicht abzählbar.
Satz 2.9 (Paradoxon des Epimenides, 6. JH v. Chr.)Epimenides [der Kreter] sagt: „Alle Kreter lügen [immer].“
Satz 2.10 (Russell’sche Antinomie, 1903)R := {T | T /∈ T}. Gilt R ∈ R?
Satz 2.11 (Gödels Unvollständigkeits-Satz, 1931)Konstruktion eines Satzes der Prädikatenlogik 2. Stufe, der aussagt, dasser selbst nicht bewiesen werden kann.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 61 / 160
Ist das wichtig?
Was ist schlimm daran, dass man nicht entscheiden kann, ob eineTuringmaschine ihre eigene Codierung akzeptiert?Ist dies ein rein theoretisches Problem?
LudwigWittgenstein1889–1951
It is very queer that this should have puzzledanyone. [. . . ] If a man says “I am lying” we saythat it follows that he is not lying, from whichit follows that he is lying and so on. Well, sowhat? You can go on like that until you areblack in the face. Why not? It doesn’t matter.
Ludwig Wittgenstein, Lectures on the Foundations ofMathematics, Cambridge 1939
Or does it?Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 62 / 160
Bedeutung der Unentscheidbarkeit
Gebt mir einen Hebel, und ich hebe die Welt ausden Angeln.
Archimedes, 3. Jh. v. Chr.
Spezielles Wortproblem W als AnsatzpunktIndirekter Beweis der Unentscheidbarkeit anderer Probleme PIdee: „Könnte ich P entscheiden, dann auch W .“
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 63 / 160
Inhalt
Turing-MaschinenEntscheidbarkeit
Unentscheidbarkeit, Diagonalisierung und das WortproblemReduktionsbeweiseDas PKP und andere unentscheidbare ProblemeSemi-EntscheidbarkeitDie universelle Turing-MaschineAbschlusseigenschaften
Berechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 64 / 160
Reduktion
„Zurückführung“ eines Problems auf ein allgemineres
Definition 2.12Eine Reduktion von L1 ⊆ Σ∗1 auf L2 ⊆ Σ∗2 ist eine mit einer TMberechenbare Funktion f : Σ∗1 → Σ∗2, so dass für alle w ∈ Σ∗1 gilt:
w ∈ L1 gdw f (w) ∈ L2
L1 ist auf L2 reduzierbar (L1 ≤ L2), wenn es eine Reduktion von L1 aufL2 gibt.
Lemma 2.13
1 Wenn L1 ≤ L2 gilt und L2 entscheidbar ist, ist L1 entscheidbar.2 Wenn L1 ≤ L2 gilt und L1 unentscheidbar ist, ist L2 unentscheidbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 65 / 160
Reduktion zum Nachweis der Entscheidbarkeit (Fall 1)
Beispiel 2.14 (Reduktion des Leerheitsproblems auf dasÄquivalenzproblem für reguläre Sprachen)
L1: Menge aller DEAs A, die die leere Sprache akzeptierenL2: Menge aller Paare (A1,A2) von DEAs, die dieselbe SpracheerkennenA{}: Trivialer DEA für leere Sprachef = A 7→ (A,A{})
Ergebnis: Da ein Algorithmus existiert, der entscheidet, ob A und A{}äquivalent sind, haben wir jetzt einen Algorithmus, der entscheidet, ob Adie leere Sprache erkennt.
Alltagsgeschäft des InformatikersZurückführung eines neuen Problemsauf ein altes, das bekanntermaßen lösbar ist
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 66 / 160
Übung: Reduktion auf ein entscheidbares Problem
Reduzieren Sie das Problem „Akzeptiert der DEA A das leere Wort?“ aufdas Wortproblem für DEAs.
L1: Menge aller DEAs A, die das leere Wort akzeptierenL2: Menge aller Paare (A,w) von DEAs A und Wörtern w mitw ∈ L(A)gesucht: f : L1 → L2 mit x ∈ L1 gdw f (x) ∈ L2
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 67 / 160
Reduktion zum Nachweis der Unentscheidbarkeit (Fall 2)
Beispiel 2.15 (Reduktion des speziellen Wortproblems auf das(allgemeine) Wortproblem für TM)
L1: Menge aller TMM, die ihre eigene Codierung c(M) akzeptierenL2: Menge aller Paare (M,w) von TMM und Wörtern w mitw ∈ L(M)f =M 7→ (M, c(M))
Zu zeigen: x ∈ L1 gdw f (x) ∈ L2.Beweis:
M∈ L1gdw M akzeptiert c(M)gdw (M, c(M)) ∈ L2
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 68 / 160
Unentscheidbarkeit des (allgemeinen) Wortproblems
Satz 2.16 (Wortproblem für Turingmaschinen)Das Wortproblem für Turingmaschinen ist unentscheidbar.
Beweis.Das spezielle WP ist auf das allgemeine WP reduzierbar. Wäre dasallgemeine WP entscheidbar, dann auch das spezielle. Wir haben aberdurch Diagonalisierung gezeigt, dass das spezielle WP unentscheidbar ist.Also kann auch das allgemeine WP nicht entscheidbar sein.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 69 / 160
Halteproblem für Turingmaschinen
Definition 2.17 (Halteproblem)Das Halteproblem ist die Menge aller Paare (M,w) vonTuringmaschinenM und Wörtern w, so dassM mit Eingabe w hält.
Satz 2.18Das Halteproblem ist unentscheidbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 70 / 160
Unentscheidbarkeit des Halteproblems
Beweis.Reduktion des Wortproblems auf das Halteproblem:
f = (M,w) 7→ (M′,w)M′ verhält sich zunächst wieM.ErreichtM eine akzeptierende Stopkonfiguration, stoppt auchM′.ErreichtM eine nicht akzeptierende Stopkonfiguration, gehtM′ ineine Endlosschleife.
Dann gilt:(M,w) ∈WP
gdw M akzeptiert wgdw M erreicht mit Eingabe w eine akzeptierende Stopkonfigurationgdw M′ hält mit Eingabe wgdw (M′,w) ∈ HP
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 71 / 160
Leerheitsproblem für Turingmaschinen
Definition 2.19 (Leerheitsproblem)Das Leerheitsproblem ist die Menge aller TuringmaschinenM, die dieleere Sprache akzeptieren.
Satz 2.20Das Leerheitsproblem ist unentscheidbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 72 / 160
Endlosschleifen-Problem
Der Beweis verwendet das Komplement des Halteproblems:
Definition 2.21 (Endlosschleifen-Problem)Das Endlosschleifen-Problem ist die Menge aller Paare (M,w) vonTuringmaschinenM und Wörtern w, so dassM mit Eingabe w nicht hält.
Satz 2.22Das Endlosschleifen-Problem ist unentscheidbar.
Beweis.Aus dem Satz zur Entscheidbarkeit des Komplements folgt, dass dasHalteproblem entscheidbar wäre, wenn das Endlosschleifen-Problementscheidbar wäre.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 73 / 160
Unentscheidbarkeit des Leerheitsproblems
Beweis.Reduktion des Endlosschleifen-Problems auf das Leerheitsproblem:
f = (M,w) 7→ M′
M′ ersetzt ihre eigene Eingabe durch wDanach verhält sichM′ wieM.
Berechnung hängt nur von w ab, nicht von ursprünglicher EingabeGleiches Resultat für alle Eingaben
Wenn eine Stopkonfiguration erreicht wird, akzeptiertM′.
Dann gilt:M hält nicht auf w
gdw M′ geht mit jeder Eingabe in Endlosschleifegdw M′ akzeptiert die leere Sprache
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 74 / 160
Äquivalenzproblem für Turingmaschinen
Definition 2.23 (Äquivalenzproblem)Das Äquivalenzproblem ist die Menge aller Paare (M,N ) vonTuringmaschinen, so dassM und N dieselbe Sprache erkennen.
Satz 2.24Das Äquivalenzproblem für Turingmaschinen ist unentscheidbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 75 / 160
Übung: Unentscheidbarkeit des Äquivalenzproblems
Zeigen Sie die Unentscheidbarkeit des Äquivalenzproblems fürTuringmaschinen, indem Sie das Leerheitsproblem auf dasÄquivalenzproblem reduzieren.
D.h.: Geben Sie eine Abbildung f von der Menge aller TM in die Mengealler Paare von TM, so dass gilt:
M∈ LP gdw f (M) ∈ ÄP
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 76 / 160
Weitere Eigenschaften von Turing-Maschinen
Alle bisher betrachteten Entscheidungsprobleme sind unentscheidbar.Ebenso das Halteproblem.Halten ist eine fundamentale Eigenschaft.Wenn man das Halteproblem nicht entscheiden kann, was dann?
Satz 2.25 (Henry Gordon Rice (1920–2003), 1953)Jede nicht-triviale semantische Eigenschaft von TM ist unentscheidbar.
nicht-trivial trifft auf einige TM zu, auf andere nichtsemantisch bezieht sich auf akzeptierte Sprache, nicht auf Maschine selbst
Beispiele 2.26 (Entscheidbare Eigenschaften)
trivial Die von der TM akzeptierte Sprache besteht aus Wörtern überdem Eingabealphabet.
syntaktisch Die TM hat 42 Zustände.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 77 / 160
Unentscheidbarkeit von semantischen Eigenschaften
Beispiel 2.27 (Eigenschaft E : TM akzeptiert Primzahlmenge P)
Behauptung: Wenn E entscheidbar ist, dann auch das HalteproblemAnsatz: Reduziere das Halteproblem auf E .
Sei E eine TM, die E entscheidet, wE eine Eingabe für E , und(A,wA) eine Instanz des Halteproblems.Definiere TM E ′ mit Eingabe wE :
1 führe Berechnung von A auf wA durchendet nach endlich vielen Schritten, wenn A auf wA hältEndlosschleife, wenn A auf wA nicht hält
2 entscheide mit Hilfe von E , ob wE ∈ P giltTeste, ob E ′ die Menge der Primzahlen akzeptiert(ist laut Annahme entscheidbar)
ja ; A hält mit Eingabe wAnein ; A hält nicht mit Eingabe wA
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 78 / 160
Inhalt
Turing-MaschinenEntscheidbarkeit
Unentscheidbarkeit, Diagonalisierung und das WortproblemReduktionsbeweiseDas PKP und andere unentscheidbare ProblemeSemi-EntscheidbarkeitDie universelle Turing-MaschineAbschlusseigenschaften
Berechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 79 / 160
Jenseits der Turing-Maschine
Bisher: Entscheidungsprobleme für Turing-MaschinenErgebnis: Kein interessantes Problem ist entscheidbarPraktische Relevanz: Hauptsächlich für Programmierer
Jetzt: Unentscheidbare Probleme aus anderen BereichenPostsches KorrespondenzproblemEntscheidungsprobleme für kontextfreie und -sensitive SprachenHilberts zweites Problem (Erfüllbarkeit in der Prädikatenlogik)
Sind die arithmetischen Axiome widerspruchsfrei?
David Hilbert, 1900
Hilberts zehntes Problem(Ganzzahlige Lösungen für Polynome mit mehreren Variablen)
Man gebe ein Verfahren an, das für eine beliebige diophantischeGleichung entscheidet, ob sie lösbar ist.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 80 / 160
Das Postsche Korrespondenzproblem
Definition 2.28 (PostschesKorrespondenzproblem)Eine Instanz des Postschen Korrespondenzproblems(PKP) ist eine endliche Folge von Paaren vonWörtern über einem endlichen Alphabet Σ:
P = ((`1, r1), (`2, r2), . . . , (`n , rn))
Eine Lösung von P ist eine Indexfolge i1, i2, . . . immit m > 0 und ij ∈ {1, . . . ,n}, so dass gilt:
`i1 · `i2 · . . . · `im = ri1 · ri2 · . . . · rim
Emil Leon Post(1897–1954)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 81 / 160
Beispiele: PKP
Sei Σ = {a, b}.1 P1 = ((a, aaa), (abaa, ab), (aab, b))Lösung 1: (2, 1)
abaaa
abaaa
Lösung 2: (1, 3)aaab
aaab
2 P2 = ((ab, aba), (baa, aa), (aba, baa))
Keine Lösung:Lösung muss mit 1 beginnen
Danach nur 3 möglich (beliebig oft)
Erstes Wort immer kürzer als zweites
ababaabaaba. . .
ababaabaabaa. . .
Nachweis, dass es keine Lösung gibt, kann sehr schwierig sein.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 82 / 160
Übung: PKP
Bestimmen Sie, falls vorhanden, die Lösungen der folgenden Instanzen desPKP.
1 P1 = ((abb, ba), (a, aabba), (aa, b), (ab, a))2 P2 = ((b, bb), (aa, aba), (a, ab))3 P3 = ((ab, aba), (a, b), (abb, bab))
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 83 / 160
Vom Halteproblem zum PKP
Ziel: Beweis der Unentscheidbarkeit des PKPMethode: Reduktion HP ≤ PKPZwischenschritt: Modifiziertes PKPReduktion HP ≤ MPKP ≤ PKP
Definition 2.29 (Modifiziertes PKP (MPKP))Eine Instanz des MPKP ist definiert wie eine Instanz des PKP.Eine Lösung des MPKP ist eine Indexfolge, die mit 1 beginnt.
Es zählen nur Lösungen, die mit dem ersten Wortpaar beginnen.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 84 / 160
Reduktion vom MPKP auf das PKP
Lemma 2.30Das MPKP kann auf das PKP reduziert werden.
Zu zeigen: Man kann eine Instanz M des MPKP in eine Instanz P desPKP übersetzen, so dass M eine Lösung hat gdw. P eine Lösung hat.Sei M = ((`1, r1), . . . , (`k , rk)) Instanz des MPKP mit Alphabet Σ.Seien | und $ Symbole, die nicht in Σ vorkommen.Definiere P = ((`′1, r ′1), . . . , (`′k , r ′k), (`′k+1, r ′k+1), (`′k+2, r ′k+2)) mit
für 1 ≤ i ≤ k:füge in `i nach jedem Symbol | einfüge in ri vor jedem Symbol | einz.B. (aba, ab) 7→ (a|b|a|, |a|b)`k+1 = |`′1, rk+1 = r ′1; z.B. (aba, ab) 7→ (|a|b|a|, |a|b)`k+2 = $, rk+2 = |$
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 85 / 160
Beispiel: Übersetzung MPKP in PKP
M = ((a, aba), (bab, b))P = ((a|, |a|b|a), (b|a|b|, |b), (|a|, |a|b|a), ($, |$))Die Lösung (1, 2) für M entspricht der Lösung (3, 2, 4) von P:
abab
abab
|a|b|a|b|$
|a|b|a|b|$
Die Folge (2, 1) erzeugt identische Wörter, beginnt aber nicht mit 1und ist deshalb keine Lösung für M .Sie erzeugt auch keine Lösung für P, da `′2 mit b beginnt und r2 mit |.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 86 / 160
Beweis der Äquivalenz
Behauptung: M hat eine Lösung gdw P hat eine Lösung.
Beweis.
⇒ Sei (i1, . . . , in) eine Lösung von M .Nach Definition des MPKP gilt i1 = 1.Dann folgt: (k + 1, i2, . . . , in , k + 2) ist Lösung von P.
⇐ Sei (i1, . . . , in) eine Lösung von P.Es gilt i1 = k + 1, da alle anderen Paare mit unterschiedlichenSymbolen anfangen.Es gibt ein t ≤ m mit it = k + 2, da alle anderen Paare mitunterschiedlichen Symbolen enden.Für das kleinste solche t gilt: (1, i2, . . . , it−1) ist Lösung von M .
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 87 / 160
Reduktion des Halteproblems auf das MPKP
Lemma 2.31Das Halteproblem kann auf das MPKP reduziert werden.
Ansatz: zu einer terminierenden Berechnung vonM auf w (HP)
c0 ` c1 ` . . . ` cn
existiert ein Lösungswort für PM,w (MPKP)
c0!c1! . . .!cn ! . . . cn+k
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 88 / 160
Wortpaare von PM,w
SeiM = (Q,Σ,Γ,∆, q0,F) und w ∈ Σ∗Alphabet für PM,w : Q ∪ Γ ∪ {!} mit ! /∈ Q ∪ Γ
Anfangsregel (!, !q0w!)Kopierregeln (a, a) für a ∈ Γ ∪ {!}Übergangsregeln (pa, qb) für (p, a, b,n, q) ∈ ∆
(pa, bq) für (p, a, b, r , q) ∈ ∆(cpa, qcb) für (p, a, b, `, q) ∈ ∆ und c ∈ Γ
(!pa, !q#b) für (p, a, b, `, q) ∈ ∆(p!, qb!) für (p,#, b,n, q) ∈ ∆(p!, bq!) für (p,#, b, r , q) ∈ ∆
(cp!, qcb!) für (p,#, b, `, q) ∈ ∆ und c ∈ Γ(!p!, !q#b!) für (p,#, b, `, q) ∈ ∆
Löschregeln (aq, q) für a ∈ Γ und Stopzustand q ∈ Q(qa, q) für a ∈ Γ und Stopzustand q ∈ Q
Abschlussregel (q!!, !) für Stopzustand q ∈ Q
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 89 / 160
Anmerkungen zur Reduktion
Ausgangskonfiguration in Wort 1, Folgekonfiguration in Wort 2Vom Übergang nicht betroffene Wortteile werden durch KopierregelnübertragenÄnderungen gemäß ∆ durch Übergangsregeln
Sonderregeln mit # bei Erreichen des BandendesAnfangsregel muss erstes Paar der MPKP-Instanz sein
für PKP gäbe es wegen Kopierregeln immer eine LösungStopzustand: Kein Übergang mit irgendeinem Bandsymbol
Reduktion setzt voraus, dass es mit jedem oder keinem Bandsymobleinen Übergang gibtkann durch 2 zusätzliche Stopzustände (einer akzeptierend, einer nichtakzeptierend) erreicht werdenähnlich Junk-Zustand bei EA
Löschregeln sind notwendig, damit nur bei einem Stopzustand dasWort akzeptiert wird
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 90 / 160
Übung: Übersetzung von Wortproblem nach MPKP
1 Erzeugen Sie eine Turing-MaschineM mit dem Alphabet {a, b}, dieauf Wörtern der Sprache a∗b∗ hält,auf anderen Wörtern nicht hält.
2 Stellen Sie sicher, dass inM jeder Zustand entweder für alle oder fürkein Bandsymbol Übergänge hat (; Stopzustand).
3 Erzeugen Sie ausM die MPKP-Instanz PM,aab.4 Verdeutlichen Sie, wie sich aus der (terminierenden) Berechung vonM auf dem Wort aab eine Lösung für PM,aab ergibt.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 91 / 160
Beweis des Lemmas
Beweis.Für eine TMM existiert eine terminierende Berechnung auf w gdw eineLösung für PM,w existiert.
⇒ Sei C eine terminierende Berechnung vonM auf wKopier- und Übergangsregeln erzeugen aus Startkonfiguration jedeFolgekonfigurationStopkonfiguration wird erreicht, da C terminiertLöschregeln löschen alle BandsymboleMit Abschlussregel wird Gleichheit der Wörter hergestellt
⇐ Sei I = (i1, . . . , ik) eine Lösung von PM,w
Wegen i1 = 1 ist Wort 2 anfangs länger als Wort 1Nur Lösch- und Abschlussregeln können LängenunterschiedverringernStopzustand wird erreicht, da Gleichheit der Wörter erreicht wird(I ist Lösung)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 92 / 160
Unentscheidbarkeit des PKP
Korollar 2.32Das MPKP und das PKP sind unentscheidbar.
PKP selbst ist kein Problem aus der Praxis des Informatikers . . .. . . aber es kann auf viele praktische Probleme reduziert werden.
Entscheidungsprobleme für kontextsensitive und kontextfreie SprachenErfüllbarkeit prädikatenlogischer Formeln
Definition 2.33 (Disjunktheitsproblem)Das Disjunktheitsproblem für kontextfreie Grammatiken (DP) ist dieMenge aller Paare (G1,G2) kontextfreier Grammatiken, für die gilt:L(G1) ∩ L(G2) = {}.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 93 / 160
Unentscheidbarkeit des Disjunktheitsproblems
Lemma 2.34Das Disjunktheitsproblem ist unentscheidbar.
Ansatz: Reduktion des PKP auf das Komplement des DPBilde Instanz P = ((`1, r1), . . . , (`k , rk)) des PKP mit Alphabet Σ abauf Instanz (G`,Gr) des DP:G` = ({S`},ΣG ,P`,S`)Gr = ({Sr},ΣG ,Pr ,Sr)ΣG = Σ ∪ {1, . . . , k}P` = {S` → `iS`i|`i i | 1 ≤ i ≤ k}Pr = {Sr → riSr i|ri i | 1 ≤ i ≤ k}
Dann gilt:L(G`) = {`i1 , . . . , `im im . . . i1 | ij ∈ {1, . . . , k}}L(Gr) = {ri1 , . . . , rim im . . . i1 | ij ∈ {1, . . . , k}}
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 94 / 160
Beispiel: Reduktion PKP ≤ DP
P = ((ab, a), (bab, ab), (b, bbb))Lösung: (1, 3, 2)abbbababbbab
G` = ({S`}, {a, b, 1, 2, 3},P`,S`)P` = {S` → abS`1|ab1|babS`2|bab2|bS`3|b3}S` → abS`1→ abbS`31→ abbbab231
Gr = ({Sr}, {a, b, 1, 2, 3},Pr ,Sr)Pr = {Sr → aSr1|a1|abSr2|ab2|bbbSr3|bbb3}Sr → aSr1→ abbbSr31→ abbbab231
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 95 / 160
Beweis der Unentscheidbarkeit
Behauptung: P hat eine Lösung gdw L(G`) und L(Gr) ein gemeinsamesElement haben
Beweis.P hat Lösung (i1, . . . , im)
gdw P hat Lösungswort `i1 · . . . · `im = ri1 · . . . · rimgdw G` erzeugt `i1 · . . . · `im · im · . . . i1 und
Gr erzeugt ri1 · . . . · rim · im · . . . i1gdw L(G`) und L(Gr) haben ein gemeinsames Element.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 96 / 160
Leerheitsproblem für kontextsensitive Sprachen
Satz 2.35 (Unentscheidbarkeit des Leerheitsproblems)Das Leerheitsproblem für kontextsensitive Sprachen ist unentscheidbar.
Beweis.Reduktion des DP auf das LP
Gegeben seien kf. Grammatiken G1,G2Konstruiere LBA A mit L(A) = L(G1) ∩ L(G2)
kontextfreie Sprachen sind auch kontextsensitivkontextsensitive Sprachen sind abgeschlossen unter Durchschnitt
Dann gilt: L(A) = {} gdw (G1,G2) ∈ DP
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 97 / 160
Äquivalenzproblem für kontextsensitive Sprachen
Satz 2.36 (Unentscheidbarkeit des Äquivalenzproblems)Das Äquivalenzproblem für kontextsensitive Sprachen ist unentscheidbar.
Beweis.Reduktion des LP auf das ÄP
Gegeben sei eine Instanz G des LPSei G{} eine kontextsensitive Grammatik, die die leere Spracheerzeugt.Dann gilt: L(G) = {} gdw L(G) = L(G{})
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 98 / 160
Äquivalenzproblem für kontextfreie Sprachen
Satz 2.37 (Unentscheidbarkeit des Äquivalenzproblems)Das Äquivalenzproblem für kontextfreie Sprachen ist unentscheidbar.
L(G`) und L(Gr) des DP sind deterministisch kontextfreikönnen durch einen deterministischen KA erkannt werden
Deterministisch kontextfreie Sprachen sind abgeschlossen unterKomplement (ohne Beweis)
Beweis.Reduktion des DP auf das ÄP
L(G`) ∩ L(Gr) = {}gdw L(G`) ⊆ L(Gr) Mengenlehregdw L(G`) ⊆ L(G) G sei KFG für L(Gr)gdw L(G`) ∪ L(G) = L(G) Mengenlehregdw L(G∪) = L(G) G∪ sei KFG für L(G`) ∪ L(G)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 99 / 160
Gültigkeitsproblem der PrädikatenlogikPrädikatenlogische Formeln
Variablen x, yKonstantensymbole c, dFunktionssymbolef (x), g(c, d)
Prädikate P(x),R(c, y)Quantoren ∀xϕ(x),∃yψ(y)Junktoren ϕ→ ψ,¬(φ ∧ ψ)
Eine Formel ϕ ist gültig wenn ϕ in jeder Interpretation wahr ist.
Definition 2.38 (Gültigkeitsproblem)Das Gültigkeitsproblem der Prädikatenlogik ist die Menge aller gültigenprädikatenlogischen Formeln.
Reduktion des PKP auf das Gültigkeitsproblem (GP):Übersetzung einer Instanz P des PKP in PL-Formel ϕP so dass gilt:P hat eine Lösung gdw ϕP ist gültig.Dann folgt: Das Gültigkeitsproblem ist unentscheidbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 100 / 160
Reduktion des PKP
Gegeben: P = ((`1, r1), . . . , (`n , rn)) mit Alphabet Σ = {a1, . . . , ak}Signatur für ϕP :
Konstantensymbol εFunktionssymbole a(1)
1 , . . . , a(1)k
Prädikat R(2)
Intuition:Domäne: Wörter über Σε: leeres Wortai(x): Konkatenation von x mit aiR(x, y): Paar (x, y) ist durch Paare von P erzeugbar
Beispiel 2.39
P = ((ab, a), (bab, ab), (b, bbb))Wort abb 7→ Term b(b(a(ε)))Paar (ab, a) 7→ Atom R(b(a(ε)), a(ε))
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 101 / 160
Formel für P
P = ((`1, r1), . . . , (`n , rn)) mit Alphabet Σ = {a1, . . . , ak}Für w = a1 · . . . · am ∈ Σ∗ sei fw(x) der Term am(. . . (a1(x)))
ϕP = ϕ1 ∧ ϕ2 → ϕ3ϕ1 =
∧i=1,...,n
R(f`i (ε), fri (ε)) Start-Paare
ϕ2 = ∀x∀y(R(x, y)→∧
i=1,...,nR(f`i (x), fri (x)) Folge-Paare
ϕ3 = ∃xR(x, x) Es gibt eine Lösung
Beispiel 2.40P = ((ab, a), (bab, ab), (b, bbb))ϕ1 = R(b(a(ε)), a(ε)) ∧ R(b(a(b(ε))), b(a(ε))) ∧ R(b(ε), b(b(b(ε))))ϕ2 = ∀x∀y(R(x, y)→
R(b(a(x)), a(x)) ∧ R(b(a(b(x))), b(a(x))) ∧ R(b(x), b(b(b(x))))ϕ3 = ∃xR(x, x)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 102 / 160
Zusammenhang zwischen PKP-Instanz und PL-Formel
P = ((ab, a), (bab, ab), (b, bbb)); Lösung: (1, 3, 2); Lösungswort: abbbab
R(b(a(ε)), a(ε)) wegen ϕ1R(b(b(a(ε))), b(b(b(a(ε))))) wegen ϕ2
R(b(a(b(b(b(a(ε)))))), b(a(b(b(b(a(ε))))))) wegen ϕ2
; ϕ3 wird wahr
Viele Interpretationen machen ϕP wahr, z.B. wenn RI = ∆I ×∆I
Nur wenn eine Lösung für P existiert, ist ϕP in allen Interpretationenwahr
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 103 / 160
Überblick unentscheidbare Probleme
SWP WP≤
HP≤
ESP
≤
LP≤
ÄP≤
nicht-triviale semantische Eigenschaft≤
MPKP
≤
PKP≤
DP≤ LP≤
ÄP≤
ÄP
≤
GPPL
≤
Turing-Maschinen / rekursiv aufzählbare Sprachenkontextsensitive Sprachenkontextfreie Sprachen
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 104 / 160
Inhalt
Turing-MaschinenEntscheidbarkeit
Unentscheidbarkeit, Diagonalisierung und das WortproblemReduktionsbeweiseDas PKP und andere unentscheidbare ProblemeSemi-EntscheidbarkeitDie universelle Turing-MaschineAbschlusseigenschaften
Berechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 105 / 160
Semi-Entscheidbarkeit
Erfüllbarkeit in Prädikatenlogik ist unentscheidbarAber: Tableau- und Resolutionsalgorithmus sind
korrekt: 2 ableitbar ; ϕ unerfüllbarwiderlegungsvollständig: ϕ unerfüllbar ; 2 ableitbar
ϕ unerfüllbar ; Algorithmus gibt nach endlicher Zeit richtige Antwortϕ erfüllbar ; Algorithmus läuft möglicherweise unendlich lange, gibtaber keine falsche AntwortWeniger als Entscheidbarkeit, aber „mehr als nichts“. . .
Definition 2.41 (semi-entscheidbar, rekursiv aufzählbar)Sei Σ ein Alphabet. Eine Sprache L ⊆ Σ∗ heißt semi-entscheidbar, wenn eseine DTM gibt, die mit Eingabe w ∈ Σ∗
terminiert, wenn w ∈ L gilt,nicht terminiert sonst.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 106 / 160
Aufzähl-Turingmaschinen
Definition 2.42 (rekursiv aufzählbar, Aufzähl-TM)Eine Sprache L ⊆ Σ∗ heißt rekursiv aufzählbar, wenn eine Aufzähl-TMexistiert, die L aufzählt.Eine Aufzähl-TM ist eine DTMM(Q,Σ,Γ,∆, q0, {}) mit den folgendenEigenschaften:
Es existiert ein Ausgabezustand qoutput ∈ Q,Wann immer der Ausgabezustand erreicht wird, gilt der Bandinhaltvon der Kopfposition bis zum ersten Symbol aus Γ \ Σ als Ausgabe.
Die vonM aufgezählte Sprache ist die Menge aller Ausgaben, die Mausgehend von q0 bei leerem Band erreicht.
Endzustandsmenge ist irrelevant:Für Semi-Entscheidbarkeit wird nur Terminierung gefordertVerwerfen entspricht EndlosschleifeAufzähl-TM testet i.d.R. alle Elemente von Σ∗ und terminiert nicht
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 107 / 160
Aufzähl-TM für ungerade Zahlen
Beispiel 2.43Modd = ({0, output}, {a}, {a,#},∆, 0, {}) zählt die Sprache{a, aaa, aaaaa, . . .} auf.
∆ =
Ausgangszustand lesen schreiben bewegen Folgezustand0 # a n outputoutput a a ` 11 # a ` 0
Übung: Geben Sie die Konfigurationsfolge vonModd bis zur drittenAusgabe an.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 108 / 160
Semi-Entscheidbarkeit und rekursive Aufzählbarkeit
Satz 2.44Eine Sprache L ∈ Σ∗ ist rekursiv aufzählbar gdw sie semi-entscheidbar ist.
Beweis „⇒“.SeiMa eine Aufzähl-TM für eine Sprache L und Σ∗ = {w1,w2,w3, . . .}.Wir definieren die TMMs wie folgt:
Eingabe w bleibt auf Eingabeband und wird nicht verändert.Auf zweitem Band startetMs das Aufzählverfahren für L und verhältsich wieMa.Wann immer der Ausgabezustand erreicht wird, wird die Ausgabe mitw verglichen
Bei Gleichheit stopptMs.Sonst fährt sie mit dem Aufzählverfahren fort.
Wenn das Aufzählverfahren terminiert, ohne dass w erzeugt wird,gehtMs in Endlosschleife.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 109 / 160
Semi-Entscheidbarkeit und rekursive Aufzählbarkeit
Beweis „⇐“.SeiMs ein Semi-Entscheidungsverfahren für L.Wir definieren eine Aufzähl-TMMa wie folgt:
1 Führe einen Schritt der Berechnung vonMs auf w1 aus.2 Führe zwei Schritte der Berechnung vonMs auf w1 und w2 aus.
. . .n Führe n Schritte der Berechnung vonMs auf w1, . . . ,wn aus.
. . .Wann immerMs auf einer Eingabe terminiert, gibtMa diese Eingabe ausund fährt dann fort.
Übung: Warum funktioniert der naive Ansatz nicht, alle Berechnungen vonMs nacheinander zu simulieren?
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 110 / 160
Dovetailing
Die im letzten Beweis verwendete Technik wird Dovetailing genannt.
verschachtelt verschiedene Berechnungenvermeidet Sackgasse, wenn eine Berechnung nicht terminiert
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 111 / 160
Semi-Entscheidbarkeit und Entscheidbarkeit
Satz 2.45Eine Sprache L ⊆ Σ∗ ist entscheidbar gdw sowohl L als auch Lsemi-entscheidbar sind.
Beweis.
⇒ SeiM eine TM, die L entscheidet, d.h. bei jeder Eingabe terminiert.Semi-EntscheidungsverfahrenM+ undM− für L bzw. L verhaltensich wieM.
WennM die Eingabe verwirft, gehtM+ in EndlosschleifeWennM die Eingabe akzeptiert, gehtM− in Endlosschleife
⇐ SeienM+ undM− Semi-Entscheidungsverfahren für L bzw. L.Eine TMM, die L entscheidet, simuliert auf zwei Bändernabwechselnd die Berechnungen vonM+ undM−.
WennM+ terminiert, akzeptiertM.WennM− terminiert, verwirftM.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 112 / 160
Inhalt
Turing-MaschinenEntscheidbarkeit
Unentscheidbarkeit, Diagonalisierung und das WortproblemReduktionsbeweiseDas PKP und andere unentscheidbare ProblemeSemi-EntscheidbarkeitDie universelle Turing-MaschineAbschlusseigenschaften
Berechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 113 / 160
Die universelle Turing-Maschine U
U ist eine DTM, die andere TM simuliert („TM-Emulator“)Nicht möglich bei bisherigen Maschinenmodellen!
da TM endliche Alphabete und Zustandsmengen haben, können sie ineinem (Binär-) Alphabet mit einer Funktion c() codiert werdenEingabe:
Codierung c(A) einer TM A,Codierung c(w) eines Eingabeworts w für A.
Mit Eingabe c(A) und c(w), verhält sich U genau wie A auf w:U akzeptiert gdw A akzeptiertU hält gdw A hältU läuft unendlich lange gdw A unendlich lange läuft
Korollar 2.46Jedes (mit TM) lösbare Problem kann in Software gelöst werden.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 114 / 160
Codierung von Turing-MaschinenCodierungsfunktion c() mit Alphabet {a, b} fürM = (Q,Σ,Γ,∆, q0,F):
Zustand c(qi) = ai c(Q) = c(q1)bc(q2)b . . . bc(qn)c(F) = c(qf1)bc(qf2)b . . . bc(qfn )
Symbol c(si) = ai c(Σ) = c(s1)bc(s2)b . . . bc(sm)c(Γ) = c(s1)bc(s2)b . . . bc(s`)
Wort c(w) = c(w|1)bc(w|2)b . . . bc(w|j)Kopf- c(`) = abewegung c(n) = aa
c(r) = aaaÜbergang c((qi , aj ,m, ak , q`)) = c(qi)bc(aj)bc(m)bc(ak)bc(q`)
c(∆) = c(δ1)bbc(δ2)bb . . . bbδkTM c(M) = c(Q)bbbc(Σ)bbbc(Γ)bbbc(∆)bbbc(q0)bbbc(F)Konfi- c(vqw) = c(v)bbc(q)bbc(w)guration
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 115 / 160
Verhalten von U
Eingabe: c(M)bbbc(w)1 codiere Startkonfiguration auf zweitem Band
Bandinhalt links von Kopfposition (#)Startzustand q0Bandinhalt beginnend mit Kopfposition (c(w))
2 finde Nachfolgekonfiguration mit Hilfe von c(M)suche Übergang (q, c, . . .) in c(M):vergleiche aktuellen Zustand q vonM mit Übergängen in c(M)vergleiche aktuelles Bandsymbol c mit Übergängen in c(M)
3 wenn kein Übergang möglich:akzeptiere, wenn q Endzustand iststoppe
4 sonst: modifiziere aktuelle Konfiguration entsprechend gefundenemÜbergang
5 weiter bei Schritt 2
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 116 / 160
Wortproblem
Satz 2.47Das Wortproblem für Turingmaschinen ist semi-entscheidbar.
Beweis.Semi-Entscheidungsverfahren für das Wortproblem (M,w):
Benutze U zur Simulation der Berechnung vonM auf w.Wenn akzeptierende Stopkonfiguration erreicht wird, stoppe.Wenn nicht akzeptierende Stopkonfiguration erreicht wird, gehe inEndlosschleife.
Korollar 2.48Das Komplement des Wortproblems ist nicht semi-entscheidbar.
Beweis.Wäre es semi-entscheidbar, wäre das Wortproblem entscheidbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 117 / 160
Leerheitsproblem
Satz 2.49
1 Das Leerheitsproblem ist nicht semi-entscheidbar.2 Sein Komplement ist semi-entscheidbar.
Beweis.
2 SeiM eine TM und (w1,w2,w3, . . .) eine Aufzählung aller Wörterüber dem Eingabealphabet.Semi-Entscheidungsverfahren für Nicht-Leerheit von L(M):
1 Führe einen Schritt der Berechnung vonM auf w1 aus.2 Führe zwei Schritte der Berechnung vonM auf w1 und w2 aus.
. . .n Führe n Schritte der Berechnung vonM auf w1, . . . ,wn aus.
. . .Stoppe, wennM eine Eingabe akzeptiert.
1 folgt aus Unentscheidbarkeit des Leerheitsproblems.Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 118 / 160
Semi-Entscheidbarkeit und ReduktionenReduktionen funktionieren auch für Semi-Entscheidbarkeit:Lemma 2.50
1 Wenn L1 ≤ L2 gilt und L2 semi-entscheidbar ist, ist L1semi-entscheidbar.
2 Wenn L1 ≤ L2 gilt und L1 nicht semi-entscheidbar ist, ist L2 nichtsemi-entscheidbar.
Beweis.
1 Semi-Entscheidungsverfahren für L1:1 Übersetze Instanz I für L1 in f (I )2 Starte Semi-EntscheidungsverfahrenM2 für L2 mit f (I )3 Terminiere, fallsM2 terminiert
2 Angenommen, L2 wäre semi-entscheidbar. Dann könnte man die fürTeil 1 skizzierte Methode verwenden, um einSemi-Entscheidungsverfahren für L1 zu erhalten.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 119 / 160
Äquivalenzproblem
Satz 2.51Weder das Äquivalenzproblem für TM noch sein Komplement istsemi-entscheidbar.
Beweis.Reduktion des Komplements des Wortproblems (WP) auf dasÄquivalenzproblem ÄP (und sein Komplement ÄP):Sei (M,w) Instanz von WP. Die DTMM′ ist wie folgt definiert:
M′ ersetzt seine Eingabe durch w, verhält sich danach wieM.AkzeptiertM, stopptM′; verwirftM, gehtM′ in Endlosschleife.
M′ akzeptiert jede Eingabe, wenn w ∈ L(M) gilt, sonst die leere Sprache.ÄP: w /∈ L(M) gdw L(M′) = {} gdw L(M′) = L(M{})
ÄP: w /∈ L(M) gdw L(M′) 6= Σ∗ gdw L(M′) 6= L(MΣ∗)M{}: DTM für leere Sprache;MΣ∗ : DTM für Σ∗.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 120 / 160
Übersicht der Entscheidungsprobleme
WP, LP und ÄP sind unentscheidbar.Aber: WP und LP sind semi-entscheidbar.
Algorithmus terminiert zumindest für eine der möglichen Antworten.Für die andere läuft er unendlich lange.
Weder ÄP noch ÄP ist semi-entscheidbar.Algorithmus liefert nie verlässlich eine Antwort.Unentscheidbarkeit von ÄP ist schwerwiegender als die von WP und LP.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 121 / 160
Übung: Äquivalenzproblem
Finden Sie den Fehler im folgenden „Beweis“ für die Semi-Entscheidbarkeitvon ÄP (Dovetailing, analog zum Beweis für LP):
Pseudo-Beweis.Gegeben seien DTMM und N mit Eingabealphabet Σ.Sei (w1,w2,w3, . . .) eine Aufzählung aller Wörter von Σ∗.
1 Führe je einen Schritt der Berechnungen vonM und N auf w1 aus.2 Führe je zwei Schritte der Berechnungen vonM und N auf w1 und
w2 aus.. . .
n Führe je n Schritte der Berechnungen vonM und N auf w1, . . . ,wnaus.. . .
WennM und N zu unterschiedlichen Antworten kommen, stoppe.Sonst fahre fort.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 122 / 160
Inhalt
Turing-MaschinenEntscheidbarkeit
Unentscheidbarkeit, Diagonalisierung und das WortproblemReduktionsbeweiseDas PKP und andere unentscheidbare ProblemeSemi-EntscheidbarkeitDie universelle Turing-MaschineAbschlusseigenschaften
Berechenbarkeit
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 123 / 160
Semi-Entscheidbarkeit und Turing-Erkennbarkeit
Lemma 2.52Eine Sprache L ist semi-entscheidbar gdw sie Turing-erkennbar ist.
Unterschied in Akzeptanzbedingung:semi-entscheidbar TM hältTuring-erkennbar TM erreicht akzeptierende Stopkonfiguration
Beweis.
⇒ SeiMS = (Q,Σ,Γ,∆, q0,F) ein Semi-Entscheidungsverfahren für L.Dann erkenntME = (Q,Σ,Γ,∆, q0,Q) die Sprache L, denn jedeStopkonfiguration ist akzeptierend.
⇐ SeiME eine TM, die L erkennt, undMdet die entsprechendedeterministische TM für L. Das Semi-EntscheidungsverfahrenMSunterscheidet sich vonME dadurch, dass es von jedem nichtakzeptierenden Endzustand in eine Endlosschleife übergeht (z.B. mitJunk-Zustand).
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 124 / 160
Abschluss unter Komplement
Satz 2.53 (Abschluss unter )Die Menge der rekursiv aufzählbaren Sprachen ist nicht abgeschlossenunter Komplement.
Beweis.
WP ist semi-entscheidbar, damit Turing-erkennbar.Wären die Turing-erkennbaren Sprachen abgeschlossen unterKomplement, wäre auch WP Turing-erkennbar und damitsemi-entscheidbar.Wären WP und WP semi-entscheidbar, wäre WP entscheidbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 125 / 160
Abschluss unter regulären Operationen und Durchschnitt
Satz 2.54 (Abschluss unter ∪, ·,∗ ,∩)Die Menge der rekursiv aufzählbaren Sprachen ist abgeschlossen unter denOperationen Vereinigung, Konkatenation, Kleene-Stern und Durchschnitt.
Beweis.Analog zu kontext-sensitiven Sprachen.Z.B. Durchschnitt: SeienM1 undM2 (deterministische) Turingmaschinenfür L1 und L2. Dann entscheidet die TMM∩ die Sprache L1 ∩ L2:
M∩ erzeugt eine Kopie der Eingabe w auf einem zusätzlichen Band.M∩ verhält sich auf dem Eingabeband wieM1.WennM1 akzeptiert, wechseltM∩ auf das zusätzliche Band undverhält sich wieM2.
Offensichtlich akzeptiertM∩ eine Eingabe w gdw sowohlM1 als auchM2 w akzeptieren.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 126 / 160
Abgrenzung von Typ-0- und Typ-1-Sprachen
Satz 2.55Es gibt Turing-erkennbare Sprachen, die nicht kontextsensitiv sind.
Beweis.Sei Σ ein Alphabet und
(G0,G1,G2, . . .) eine Aufzählung aller ks. Grammatiken über Σ,(w0,w1,w2, . . .) eine Aufzählung aller Wörter über Σ.
(Diese Aufzählungen sind mit TM realisierbar.)
L := {wi | wi /∈ L(Gi)} (Diagonalisierung!)
L ist entscheidbar (Typ 0):Zähle G0,G1, . . . ,Gi aufZähle w0,w1, . . . ,wi aufEntscheide WP (L(Gi),wi)
L ist nicht kontextsensitiv (Typ 1):Sonst gibt es k mit L = L(Gk)wk ∈ L = L(Gk)wk /∈ L(Gk) Def. L
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 127 / 160
Zusammenfassung: Entscheidbarkeit
Gödelisierung: Codierung einer TM als Eingabe für TMTuring: Unentscheidbarkeit von WP und HP (Diagonalisierung)Unentscheidbarkeitsbeweise durch ReduktionRice: Alle interessanten Probleme für TM sind unentscheidbarUnentscheidbare Problem aus anderen Bereichen
PKPkontextfreie und kontextsensitive SprachenErfüllbarkeit in der Prädikatenlogik
Semi-Entscheidbarkeit und rekursive AufzählbarkeitAufzähl-TMWP und LP zumindest semi-entscheidbar
Simulation von TM durch universelle TM UAbschlusseigenschaften: Alles außer Komplement
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 128 / 160
Überblick Spracheigenschaften
Eigenschaft regulär kontextfrei kontext- rekursivsensitiv aufzählbar
(Typ 3) (Typ 2) (Typ 1) (Typ 0)Abschluss∪, ·,∗ 3 3 3 3
∩ 3 7 3 3
3 7 3 7
EntscheidbarkeitWort 3 3 3 7
Leerheit 3 3 7 7
Äquivalenzproblem 3 7 7 7
Äquivalenzdeterministisches und 3 7 ? 3
nicht-deterministischesModell
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 129 / 160
Inhalt
Turing-MaschinenEntscheidbarkeitBerechenbarkeit
Turing-BerechenbarkeitWHILE-ProgrammeDie Church-Turing-These
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 130 / 160
Inhalt
Turing-MaschinenEntscheidbarkeitBerechenbarkeit
Turing-BerechenbarkeitWHILE-ProgrammeDie Church-Turing-These
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 131 / 160
Turingmaschinen mit Ausgabe
Bisher: TM erkennt SpracheEingabe wird akzeptiert oder verworfen (gemäß F)
akzeptierende Stopkonfigurationnicht akzeptierende Stopkonfiguration oder unendliche Berechnung
Nur zwei mögliche Antworten
Jetzt: TM berechnet FunktionTM kann Band beschreiben ; Ausgabe erzeugennicht möglich / sinnvoll bei EA, KA und LBAAnalog zu Funktionen in Programmiersprachen
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 132 / 160
Turing-BerechenbarkeitBerechnende TM ist immer deterministisch
Funktionswert sonst nicht eindeutigAusgabe: Bandinhalt, wenn TM stoppt
von Kopfpositionbis zum ersten Symbol aus Γ \ Σ
Endzustandsmenge irrelevantUnendliche Berechnung entspricht nicht definiertem Funktionswert
erlaubt partielle Funktionen
Definition 3.1 (Turing-berechenbar)Eine partielle Funktion f : (Σ∗)n → Σ∗ heißt Turing-berechenbar, wenn eseine DTMM gibt, so dass für jedes Tupel (w1, . . . ,wn) ∈ dom(f ) mitf (w1, . . . ,wn) = x gilt:
M terminiert ausgehend von Startkonfiguration q0w1#w2# . . .#wn .Die Stopkonfiguration hat die Form uqxvy mit
u, y ∈ Γ∗v ∈ Γ \ Σ
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 133 / 160
Beispiel: Addition
Mathematische Funktionen werden oft unär mit Σ = {a} dargestelltak entspricht k
Beispiel 3.2Die TM A berechnet die Summe zweier Zahlen
A = ({0, 1, 2, 3}, {a}, {a,#},∆, 0, {})
∆ =
Ausgangszustand lesen schreiben bewegen Folgezustand0 a a r 00 # a ` 11 a a ` 11 # # r 22 a # r 3
Übung: Welche Berechnungen führt A mit den Eingaben aaa#aa, #aa,## durch? Welche Ausgaben werden erzeugt?
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 134 / 160
Übung: Subtraktion
Geben Sie eine TM S an, die die modifizierte Differenz, also die folgendeFunktion .− : N2 → N berechnet.
x .− y ={
x − y wenn y ≤ x0 sonst
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 135 / 160
Berechenbarkeit und Entscheidbarkeit
Definition 3.3 (Charakteristische Funktion)Für eine Trägermenge T und eine Teilmenge M ⊆ T ist diecharakteristische Funktion von M die Funktion χM : T → B mit
χM (x) ={
1 wenn x ∈ M0 sonst
Satz 3.4Eine Menge M ist entscheidbar gdw. χM berechenbar ist.
Beweis.⇒ Wenn Eingabe akzeptiert wurde, schreibe a, sonst schreibe #, stoppe.⇐ Wenn Stopkonfiguration erreicht ist, lies aktuellen Bandinhalt.
Falls Inhalt gleich a ist: akzeptiere, sonst verwerfe.Da χM total ist, terminiert die Berechnung für jede Eingabe.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 136 / 160
Inhalt
Turing-MaschinenEntscheidbarkeitBerechenbarkeit
Turing-BerechenbarkeitWHILE-ProgrammeDie Church-Turing-These
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 137 / 160
Die Programmiersprache WHILE
an imperative Programmiersprachen angelehntes Berechnungsmodellgleich mächtigauf notwendige Anweisungen reduziert
gleich mächtig wie Turingmaschinen
Syntax-Elemente:Variablen x0, x1, x2, . . .
Konstanten 0, 1, 2, . . .Zuweisungsoperator :=
Kompositionsoperator ;Arithmetische Operatoren +, .−
Schlüsselwörter while, do, end
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 138 / 160
WHILE-Syntax
Definition 3.5 (Syntax von WHILE-Programmen)Die Syntax von WHILE-Programmen ist wie folgt induktiv definiert:
1 Wertzuweisung Für i, j, c ∈ N sindxi := xj + c und xi := xj
.− cWHILE-Programme.
2 Komposition: Sind P1 und P2 WHILE-Programme, dann auchP1; P2
3 While-Schleife: Ist P ein WHILE-Programm und i ∈ N, dann auchwhile xi do P end
Übung: geben Sie eine kontextfreie Grammatik für WHILE-Programme an.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 139 / 160
WHILE-Semantik
Definition 3.6 (Semantik von WHILE-Programmen)Bei einem WHILE-Programm mit n Eingabewerten
enthalten die Variablen x1, . . . , xn die Eingabewerte;haben alle anderen Variablen den Wert 0;ist die Ausgabe der Inhalt der Variable x0 nach Programmende.
Die Programmkonstrukte haben folgende Bedeutung:1 xi := xj + c / xi := xj
.− cDer neue Wert von xi ist die Summe / die modifizierte Differenz desalten Werts von xj und der Konstanten c.
2 P1; P2Es wird zuerst P1, danach P2 ausgeführt.
3 while xi do P endEs wird so lange P ausgeführt, bis xi den Wert 0 erreicht.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 140 / 160
WHILE-Berechenbarkeit
Definition 3.7 (WHILE-berechenbar)Eine (partielle) Funktion f : Nk heißt WHILE-berechenbar, falls es einWHILE-Programm P gibt, für das gilt:
Wenn P mit den Eingabewerten n1, . . . ,nk in den Variablenx1, . . . , xk gestartet wird,terminiert P, falls f (n1, . . . ,nk) definiert ist, mit dem Wert vonf (n1, . . . ,nk) in der Variablen x0.Sonst terminiert P nicht.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 141 / 160
Kontrollstrukturen: LOOP / FOR
Alle Kontrollstrukturen aus anderen Programmiersprachen können mitWHILE-Programmen realisiert werden.
Beispiel 3.8 (LOOP-Schleife)loop xi do P end: Schleife mit fester Anzahl xi von Durchläufen1: xj := xi + 0;2: while xj do3: xj := xj
.− 1;4: P5: end
xj wird sonst nicht benutzt
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 142 / 160
Kontrollstrukturen: IF
Beispiel 3.9 (IF-THEN-ELSE-Konstrukt)if xi then P1 else P2 end: Wenn xi 6= 0 gilt, wird P1 ausgeführt, sonst P21: loop xi do2: xj := x` + 1 // xi 6= 0 ; xj = 13: end;4: xk := x` + 1;5: loop xj do6: xk := x` + 0 // xj 6= 0 ; xk = 07: end;8: loop xj do9: P1 // xj 6= 0 ; P1 wird ausgeführt
10: end;11: loop xk do12: P2 // xk 6= 0 ; P2 wird ausgeführt13: endxj , xk , x` werden sonst nicht benutzt
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 143 / 160
Arithmetik mit WHILE
Beispiel 3.10(Variablen-Addition)
Eingabe: x1, x2: SummandenAusgabe: x0: Summe x1 + x21: x0 := x1 + 0;2: loop x2 do3: x0 := x0 + 14: end
Beispiel 3.11 (Multiplikation)
Eingabe: x1, x2: FaktorenAusgabe: x0: Produkt x1 · x21: loop x1 do2: x3 := x2 + 0;3: loop x3 do4: x0 := x0 + 1;5: end6: end
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 144 / 160
Übung: WHILE-Programme
Schreiben Sie WHILE-Programme für die Ganzzahl-Division DIV und denModulo-Operator MOD.
14 DIV 3 = 4,14 MOD 3 = 2.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 145 / 160
Eine partielle Funktion
Beispiel 3.12 (Variablen-Subtraktion)
s : N2 → N mit s(x, y) ={
x − y wenn x ≥ yundefiniert sonst
Die Funktion s ist WHILE-berechenbar:
1: while x2 do // Solange x2 > 0 gilt2: if x1 then // Wenn x1 > 0 gilt3: x1 := x1
.− 1;4: x2 := x2
.− 1 // dekrementiere x1 und x2 parallel5: end6: end; // terminiert nicht, wenn x2 > x1 gilt7: x0 := x1 + 0
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 146 / 160
WHILE-Programme und Programmiersprachen
WHILE bietetKontrollstruktur whileAddition und Subtraktion für natürliche ZahlenDamit simulierbar:
Kontrollstrukturen FOR, IF, . . .Gleitkommazahlenkomplexe mathematische OperationenOperationen auf anderen Datentypen (Strings, Pointer, Objekte,. . . )
Korollar 3.13Alle Funktionen, die mit existierenden Programmiersprachen (Java, C,Python, Prolog, Lisp, . . . ) berechenbar sind, sind auchWHILE-berechenbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 147 / 160
Simulation von WHILE-Programm durch Turingmaschine
Satz 3.14Jede WHILE-berechenbare Funktion ist auch Turing-berechenbar.
Beweis.Simuliere WHILE-Programm P mit k Variablen durch (k + 1)-Band-TMMP :
1 Eingabevektor x1#x2# . . .#xk auf Band 12 Kopiere xi auf Band i + 1 für 1 ≤ i ≤ k; lösche Band 13 Simuliere einzelne Schritte:
xi := xj + / .− c: Führe Operation auf Band i + 1 ausP1; P2: Simuliere erst P1, dann P2while xi do P1 end:
Wenn Band i + 1 leer ist, terminiereSonst simuliere P1, beginne von vorn
4 Spule Band 1 an den Anfang zurück (Ausgabevariable x0)(Wird nur ausgeführt, wenn P terminiert)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 148 / 160
Simulation von Turingmaschine durch WHILE-Programm
Satz 3.15Jede Turing-berechenbare Funktion ist auch WHILE-berechenbar.
Beweis.Simuliere TMM = (Q,Σ,Γ,∆, q0,F) durch WHILE-Programm PM:Sei Q = {q0, . . . , qn} und Γ = {γ1, . . . , γk}.Codierung einer Konfiguration αqiβ durch 3 Variablen x1, x2, x3:
x2 = i codiert Zustandx1 und x3 codieren α und β:
Symbol ci codiert als iWort w ∈ Γ` codiert als Zahl zur Basis k + 1ci1 · ci2 · . . . · ci`
7→ i1 · k0 + i2 · k1 + . . .+ i` · k`−1
z.B. k = 9, dann gilt: γ3 · γ5 · γ4 · γ1 7→ 1453Lese- und Schreiboperationen sowie Kopfbewegungen möglich mit DIVund MOD
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 149 / 160
Simulation von Turingmaschine durch WHILE-Programm
Beweis (Fortsetzung).Arbeitsweise von PM:
1 Codiere Eingabe in Startkonfiguration2 WHILE-Schleife
1 Decodiere aktuelles Symbol c (aus x3 MOD k + 1) und q aus x22 Teste, ob es eine Folgekonfiguration mit Zustand q und Symbol c gibt
ja: ändere x1, x2, x3 entsprechendnein: beende WHILE-Schleife
3 decodiere Ausgabe aus x3 und schreibe Wert in x0(wird nur ausgeführt, wennM terminiert)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 150 / 160
Inhalt
Turing-MaschinenEntscheidbarkeitBerechenbarkeit
Turing-BerechenbarkeitWHILE-ProgrammeDie Church-Turing-These
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 151 / 160
Äquivalenz verschiedener Berechnungsmodelle
Wir haben gezeigt:Äquivalenz zwischen Turingmaschinenund WHILE-ProgrammenÄquivalenz zwischen While-Programmenund Java/C/Lisp/Prolog-Programmen
Man kann außerdem Äquivalenz zeigen zuµ-rekursiven Funktionenλ-Kalkül (Church)von-Neumann-Rechnerrealen Prozessoren/Computern
Alonzo Church(1903–1995)
Ergebnis:Alle existierenden Berechnungsmodelle und Computer sind äquivalentzur TM (oder schwächer).
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 152 / 160
Die Church-Turing-These
A function is effectively calculable if its values can be found bysome purely mechanical process.A computable function is a function calculable by a machine.The classes of effectively calculable functions and computablefunctions are identical.
Alan Turing, 1939
effectively calculable durch einen Algorithmus berechenbarohne Rückgriff auf Intuitionoder Verständnis des Problems
computable durch eine Turingmaschine berechenbar
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 153 / 160
Zusammenfassung der bisherigen Ergebnisse
Turing: Das Halteproblem für TM ist unentscheidbar.Rice: Jede nicht-triviale semantische Eigenschaft von TM ist
unentscheidbar.Church-Turing: Jeder existierende Computer und jedes Berechnungsmodell
ist äquivalent zur TM (oder schwächer).Turing: Erfüllbarkeit von prädikatenlogischen Formeln ist
unentscheidbar.
Konsequenzen
Keine interessante Eigenschaft von Programmen in irgendeinermächtigen Programmiersprache ist entscheidbar.Zahlreiche wichtige Probleme außerhalb der Informatik sindunentscheidbar.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 154 / 160
Unentscheidbare Probleme in der Praxis
Innerhalb der Informatik:SW-Engineering Erfüllt das Programm eine formale Spezifikation?
Debugging Hat das Programm ein Speicherleck?Malware Richtet das Programm Schaden an?Studium Berechnet das Programm des Studenten dieselbe
Funktion wie die Musterloesung?
Außerhalb der Informatik:Formale Sprachen Erzeugen zwei kf. Grammatiken dieselbe Sprache?
Mathematik Hilberts zehntes Problem: Ganzzahlige Lösungen fürPolynome mit mehreren Variablen
Logik Automatisierung von Beweisen
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 155 / 160
Praktische Relevanz
Ja, diese Problemetreten in der Praxisauf. . .
(stackexchange.com)
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 156 / 160
Nochmal: Ist das wichtig?
It is very queer that this should have puzzledanyone. [. . . ] It doesn’t matter.
Wittgenstein
Yes, it does matter!
Church,Turing
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 157 / 160
Was bleibt möglich?
Es ist möglich denn
ein Programm P aus einer Spra-che in eine andere zu übersetzen
ein spezielles Programm wird für P er-zeugt.
festzustellen, ob ein Programmeinen Befehl enthält, auf dieFestplatte zu schreiben
dies ist eine syntaktische Eigenschaft.Unentscheidbar ist, ob dieser Befehl ir-gendwann ausgeführt wird.
zur Laufzeit zu prüfen, ob einProgramm auf die Festplattezugreift
dies entspricht einer Simulationdurch U . Es ist unentscheidbar, ob derZugriff nie ausgeführt wird.
ein Programm zu schreiben, dasin allen „wichtigen“ Fällen dierichtige Antwort gibt
es wird immer Fälle geben, in denengar keine oder eine falsche Antwort ge-geben wird.
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 158 / 160
Was kann man tun?Kann man die Turingmaschine „reparieren“?
Der Beweis für die Unentscheidbarkeit verwendet keine spezifischenCharakteristika der TM.Einzige Voraussetzung: Existenz der universellen TM UAndere Maschinenmodelle haben dasselbe Problem (oder sindschwächer).Die TM ist nicht zu schwach, sondern zu stark
Auswege:Wenn möglich: schwächere Formalismen verwenden
für formale Sprachen: Reguläre Ausdrücke, kontextfreie Grammatikenin der Logik: Modallogik, Dynamische Logik
Heuristiken verwenden, die in vielen Fällen funktionieren;verbleibende Fälle manuell lösen
PL-Resolution mit TimeoutJan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 159 / 160
Zusammenfassung: Berechenbarkeit
TM kann Ausgaben erzeugen und Funktionen berechnenWHILE: Minimale Programmiersprache
äquivalent zu TMäquivalent zu realen Programmiersprachen / Computern
Church-Turing-These: TM ist äquivalent zu jedem mächtigenBerechnungsformalismus und MaschinenmodellKeine interessante Eigenschaft für irgendeine Programmiersprache istentscheidbarKeine existierende oder zukünftige Programmiersprache kann die fürTM unentscheidbaren Probleme entscheiden
Konsequenzen:Computer können Informatikern nicht alle Arbeiten abnehmen. /Computer werden Informatiker nie überflüssig machen. ,
Jan Hladik (DHBW Stuttgart) Formale Sprachen und Automaten Sommersemester 2019 160 / 160