Theoretische InformatikAutomaten und formale Sprachen

Prof. Dr. Sibylle SchwarzHTWK Leipzig, Fakultät IMN

Gustav-Freytag-Str. 42a, 04277 LeipzigZimmer Z 411 (Zuse-Bau)

http://www.imn.htwk-leipzig.de/~schwarzsibylle.schwarz@htwk-leipzig.de

Wintersemester 2015/16

1

Einordnung der Theoretischen InformatikInformatik Lehre von der Darstellung und Verarbeitung von

Information durch Algorithmen

Teilgebiete der Informatik:

theoretisch I Sprachen zur Formulierung von Information undAlgorithmen,

I Möglichkeiten und Grenzender maschinellen Berechenbarkeit,

I Grundlagen für technische und praktische(und angewandte) Informatik

technisch I maschinelle Darstellung von InformationI Mittel zur Ausführung von Algorithmen

(Rechnerarchitektur, Hardware-Entwurf, Netzwerk, . . . )

praktisch Entwurf und Implementierung von Algorithmen(Betriebssysteme, Compilerbau, SE, . . . )

angewandt Anwendung von Algorithmen(Text- und Bildverarbeitung, Datenbanken, KI, Medizin-,Bio-, Wirtschafts-, Medieninformatik, . . . )

2

Anwendungen der theoretischen InformatikFormale Sprachen

I Repräsentation von Problemen in maschinenlesbarer Form(Mensch-Maschine-Kommunikation, Modellierung)

I Ausdrucksstärke und Flexibilität von ProgrammiersprachenI Übersetzung von Programmiersprachen (z.B. in ausführbaren Code)

Maschinenmodelle (Automaten)I Möglichkeiten und Grenzen verschiedener Modelle zur Ausführung

von Algorithmen

Berechenbarkeitstheorie (hier Ausblick, mehr dazu im Mastermodul)I Welche Probleme sind überhaupt algorithmisch

(mit Hilfe verschiedener Maschinenmodelle) lösbar?Auch negative Antworten sind sehr hilfreich(sparen Aufwand für ungeeignete Lösungsansätze)

Komplexitätstheorie (hier Ausblick, mehr dazu im Mastermodul)I Welche Probleme sind mit beschränkten Ressourcen

(z.B. Zeit, Speicherplatz) lösbar?I Für welche Probleme können schnelle Algorithmen existieren?

3

Prinzipien der theoretischen Informatikältester Zweig der Informatik (lange vor dem ersten Computer)Mathematische Prinzipien:

I AbstraktionI ermöglicht verallgemeinerte Aussagen und breit einsetzbare

Verfahren,I Ergebnisse und Verfahren oft nicht sofort praktisch anwendbar,

müssen auf spezielle Situationen angepasst werden.I Beweisbarkeit

I erfordert präzise Modellierung des ProblemsI Nachweis der Korrektheit von Hard- und Software

(Tests können dies nicht !)

Wissen aus der theoretischen InformatikI veraltet über viele Jahre kaumI Grundlage für Verständnis von (schnelllebigem) Spezialwissen,

z.B. konkrete Programmiersprachen, Domain-spezifischeSprachen, Transformationen

4

Aus der Modulbeschreibung3010 Theoretische Informatik: Automaten und formale Sprachen

Arbeitsaufwand: Präsenzzeit 60 h (= 2 h V + 2 h Ü je Woche)Vor- und Nachbereitungszeit 90 h (≈ 6 h je Woche)

Voraussetzungen: anwendungsbereite Kenntnisse auf den GebietenModellierung, Logik, Algorithmen undDatenstrukturen, Aufwandsabschätzungen

Lernziele: Die Studierenden sind in der Lage, wichtige Klassenformaler Sprachen als Grundlage von Programmier-und Beschreibungssprachen einzuordnen und kennendie wesentlichen Eigenschaften der Sprachklassen.Sie kennen die entsprechenden abstraktenMaschinenmodelle und Algorithmen und können siezur Darstellung und Lösung praktischerAufgabenstellungen einsetzen.Die Studierenden wissen, dass nicht jedes formaldarstellbare Problem algorithmisch lösbar ist.

5

Inhalt der LehrveranstaltungI Formale Sprachen

I Wiederholung: Alphabet, Wort, Sprache, Operationen daraufI reguläre AusdrückeI Wiederholung: WortersetzungI Grammatiken, Chomsky-Hierarchie

I MaschinenmodelleI Endliche AutomatenI KellerautomatenI Turing-Maschinen

I Berechenbarkeit (Ausblick auf Master-Modul)I berechenbare FunktionenI BerechnungsmodelleI These von ChurchI algorithmische Entscheidbarkeit / Unentscheidbarkeit

I Komplexität (Ausblick auf Master-Modul)I KomplexitätsmaßeI Komplexitätsklassen P, NP, PSPACE

jeweils mit vielen Beispielen6

LiteraturI Uwe Schöning:

Theoretische Informatik - kurzgefasst (Spektrum 2001)I John E. Hopcroft, Jeffrey D. Ullman:

Einführung in die Automatentheorie, Formale Sprachen undKomplexitätstheorie (Addison-Wesley 1990)

I Dirk W. Hoffmann:Theoretische Informatik (Hanser 2009)

I Rolf Socher:Theoretische Grundlagen der Informatik (Hanser 2008)

I Ulrich Hedtstück:Einführung in die Theoretische Informatik (Oldenbourg 2007)

I Gottfried Vossen, Kurt-Ulrich Witt:Grundkurs Theoretische Informatik (Vieweg 2006)

I Alexander Asteroth, Christel Baier:Theoretische Informatik. Eine Einführung in Berechenbarkeit,Komplexität und formale Sprachen (Pearson 2002)

I Renate Winter:Theoretische Informatik (Oldenbourg 2002)

7

Lehrveranstaltungen

Folien, Übungsserien, aktuelle Informationen unterwww.imn.htwk-leipzig.de/~schwarz/lehre/ws15/ti

Vorlesung jeden Freitag (2 h / Woche)Selbststudium (Hausaufgaben): (6 h / Woche)

schriftliche Übungsserien (ca. zu jeder Vorlesung)Besprechung in der nächsten Übung

Autotool je Freitag bis DonnerstagÜbung (2 Gruppen) jeden Dienstag: (2 h / Woche)

alle Folien, Aufgaben, Lösungen mitbringen !I Besprechung der Übungsserien (Vorrechnen),I Fragen zum aktuellen Vorlesungsinhalt

8

Prüfung

Prüfungsvorleistungen:I ≥ 50% aller Punkte für

Autotool-Pflichtaufgaben undI ≥ 3 Vorrechen-Punkte (Übungen)

Prüfung: Klausur 90 minAufgabentypen ähnlich Übungsaufgaben(Hilfsmittel: beidseiting handbeschriebenes A4-Blatt)

9

Formale Sprachen

Syntax natürlicher Sprachen:I Rechtschreibung: korrekte WörterI Grammatik: Aufbau korrekter Sätze

Definition von Programmiersprachen:Syntax Form der Sprachelemente

Semantik Bedeutung der Sprachelemente und -strukturenPragmatik Regeln zur zweckmäßigen Anwendung

Syntax von Programmiersprachen:I Schlüsselwörter, Bezeichner, Darstellung von Zahlen, . . .I Programmstrukturen:

Form der Ausdrücke, Anweisungen, Deklarationen, . . .

10

Formale Sprachen: BeispieleProgrammiersprachen:

while (b != 0) { if (a > b) a = a - b; else b = b - a; }

Regeln für korrekte Syntax (EBNF):

Statement ::= ... | IfStmt | WhileStmt | ... ;WhileStmt ::= "while" "(" Expr ")" Statement;IfStmt ::= "if" "(" Expr ")" Statement ( "else" Statement )?;Expr ::= ...

Domain-spezifische Sprachen , z.B. Autotool-Lösungen zu AL-ModelllistToFM[(x,True),(y,False),(z,False)]

Regeln für korrekte Syntax (EBNF):

belegung ::= "listToFM" "[" var-wert-paare "]"var-wert-ps ::= "" | var-wert-paar | var-wert-paar "," var-wert-psvar-wert-paar ::= "(" var-name, wert ")"wert ::= "True" | "False"var-name ::= ...

Graphische Sprachen , z.B.11

Maschinenmodell: endlicher Automat

Beschreibung des dynamischen Verhaltens von Systemen

Modellierung von Abläufen (Zustandsübergangssysteme)

Beispiele:I Bedienoperationen an Geräten oder SoftwareI Schaltfolgen von AmpelanlagenI Steuerung von ProduktionsanlagenI Ablauf von (Geschäfts-)Prozessen

12

Beispiel: (Pool-)Einlass mit Karte

Automat definiert durchI Zustände: gesperrt, freiI Startzustand: gesperrtI Aktionen (Eingabesymbole): Karte (anlegen), Durchgehen,

TimeoutI Zustandsübergänge(gesperrt, Karte) → frei

(frei, Karte) → frei(frei, Durchgehen) → gesperrt(frei, Timeout) → gesperrt

definiert mögliche (erlaubte) Folgen von Aktionen

Diese Folgen lassen sich durch reguläre Ausdrücke darstellen:( Karte Karte∗( Durchgehen + Timeout ))∗

13

Anwendung bei der Übersetzung von Programmen

Übersetzung von Quell- in Zielsprache(z.B. C, Java in Maschinen- oder Byte-Code)

meist in zwei Phasen über eine (gemeinsame) Abstraktion:

Quellcode↓ Analyse-Phase (Front-End)

Zwischendarstellung(oft Baumstruktur)

↓ Synthese-Phase (Back-End)Code in Zielsprache

14

Analyse-Phase

Quellcode Scanner Folge von Token Parser Syntaxbaum

lexikalische Analyse (Scanner)lineare Analyse des Quelltextes,Aufteilung in Einheiten (Token)z.B. Schlüsselwörter, Bezeichner, Zahlenreguläre Sprachen, endliche Automaten

Syntaxnalyse (Parser)hierarchische Struktur des Quelltextesz.B. Ausdrücke, Verzweigungen, Schleifenkontextfreie Sprachen, Kellerautomaten

semantische Analyse Annotationen im Syntaxbaum,z.B. Typprüfungen

15

Einsatz ähnlicher Transformations- und Analyse-MethodenI Compiler für Programmiersprachen (z. B. Java → Bytecode)I Interpreter für Programmiersprachen (z. B. Java-Bytecode)I Übersetzung von Daten zwischen verschiedenen Formaten

z. B. LilyPond (http://www.lilypond.org) übersetzt\repeat volta 3 { c’ e’ g’ e’ | }\alternative { { c’2 g’ | } { g’1 | } }

u. A. inI Verarbeitung von Domain-spezifischen SprachenI TextformatierungI DokumentbeschreibungssprachenI kontextabhängige Hilfe in EntwicklungsumgebungenI statische Analyse zur Fehlersuche in ProgrammenI graphische Editoren (z.B. für UML-Diagramme) mit

automatischer Programmgenerierung16

Berechenbarkeit / Entscheidbarkeit

Halteproblem:Kann ein (Test-)programm U existieren, welches für jedes beliebige(Dienst-)Programm P (Eingabe als Quelltext) entscheidet, ob Pnach endlich vielen Schritten anhält?

Nein

Folgerungen:I Alle Versuche, ein solches Programm zu schreiben, müssen

fehlschlagen.I Suche nach Verfahren, die für eine möglichst große Teilmenge

aller (Dienst-)Programme P entscheiden, ob P nach endlichvielen Schritten anhält, ist sinnvoller.

I Entwickler von P (Dienstleister) muss nachweisen, dass seinProgramm P nach endlich vielen Schritten anhält

17

KomplexitätBeispiel Primzahltest

Problem: Ist eine gegebene Zahl n eine Primzahl?

Instanz des Problems: Ist 12347 eine Primzahl?

lösbar durch den Algorithmus:1. Für alle i ∈ {2, . . . , n}:

Test: Ist n durch i teilbar?I ja: Ende mit Ausgabe n ist nicht prim.I nein: weiter (mit Test für i + 1)

2. Ausgabe: n ist prim.

Test ist für große Zahlen aufwendig. Geht es besser?

I Was bedeutet aufwendig und besser?I Wie aufwendig ist eine Berechnung?I Wie aufwendig ist die Lösung eines Problemes?

18

Wiederholung: Alphabet, Wort, SpracheFür jede Menge A heißt

An = A× · · · × A︸ ︷︷ ︸n

= {w1 · · ·wn | ∀i : wi ∈ A}

Menge aller Wörter der Länge n über A(n-Tupel, Vektoren, Folgen, Listen, Zeichenketten)

A∗ =⋃{n∈N} A

n Menge aller Wörter über A(endliche Folgen, Listen, Zeichenketten)

A0 = {ε} mit leerem Wort ε

Alphabet (endliche) Menge A von SymbolenWort endliche Folge von Symbolen w = w1 · · ·wn mit

∀i ∈ {1, . . . , n} : wi ∈ A

Länge eines Wortes |w | = Anzahl der Symbole in w

Anzahl der Vorkommen eines Symboles in einem Wort|w |a = Anzahl der a in w (für a ∈ A)

Sprache Menge von Wörtern L ⊆ A∗

19

Beispiele

I Alphabet A = {0, 1}Wörter ∈ A∗ = {0, 1}∗: Menge aller Binärwörter

Sprachen ⊆ A∗, z.B.I {w ∈ {0, 1}∗ | w1 6= 0} Menge aller Binärzahlen

ohne führende NullenI {w ∈ {0, 1}∗ | w1 6= 0 ∧ w|w |−1 = w|w | = 0}

Menge aller Binärdarstellungen durch 4 teilbarerZahlen ohne führende Nullen

I Alphabet A = {a, b}Wörter ∈ A∗ = {a, b}∗: Menge aller Wörter, die

höchstens die Buchstaben a und b enthaltenSprachen ⊆ A∗, z.B.

I ∅I {a, b}I {a}∗ = {ε, a, aa, aaa, . . .}I {w ∈ {a, b}∗ | w1 = a ∧ w|w | = a} ={a, aa, aaa, aba, aaaa, abaa, aaba, abba, . . .}

20

Beispiele für SprachenI Menge aller englischen Wörter L1 ⊂ {a, . . . , z}∗

I Menge aller deutschen Wörter L2 ⊂ {a, . . . , z , ß,ä,ö,ü}∗

I Menge aller möglichen DNA L3 ⊆ {A,T ,G ,C}∗

I Menge aller natürlichen Zahlen in DezimaldarstellungL4 ⊆ {0, . . . , 9}∗ (evtl. mit führenden Nullen)

I Menge aller natürlichen Zahlen in Binärdarstellung(Bitfolgen beliebiger Länge) L5 ⊆ {0, 1}∗

I Menge aller aussagenlogischen Formeln in AL({p, q, r})L6 ⊆ {p, q, r , t, f,¬,∨,∧,→,↔, (, )}∗,

I Menge aller arithmetischen Ausdrücke über Z (ohne Variablen)L7 ⊂ {0, . . . , 9,+, ·,−, /, (, )},

I Menge aller deutschen Sätze L8 ⊂ (L2 ∪ {., , , !, ?, (, ),−})∗

Wie lassen sich unendliche Sprachen endlich darstellen?(Voraussetzung für maschinelle Verarbeitung)verschiedene Darstellungen später in dieser LV

21

Darstellung von Wörtern

extensional durch Angabe der Symbole in ihrer ReihenfolgeBeispiele: u = 321,v = abababababa,w = w1 · · ·w4 mit w1 = w2 = w3 = a, w4 = b

intensional durch Angabe einer Eigenschaft, die für jeden Index idas i-te Symbol eindeutig bestimmt.

Beispiele:u ∈ {0, . . . , 4}3 mit ∀i ∈ {1, . . . , 3} : ui = 4− i ,

v ∈ {a, b}11 mit ∀i ∈ {1, . . . , 11} : vi =

{a falls i ∈ 2N+ 1b sonst

w ∈ {a, b}4 mit w4 = b ∧ ∀i ∈ {1, . . . , 3} : wi = a

22

Darstellung von Sprachen

extensional durch Angabe der Elemente(nur Beschreibung endlicher Sprachen möglich)Beispiele: {ε, a, aa, aaa}, {b, ba, baa, baaa},{a, b, aa, bb, aaa, bbb}

intensional durch Angabe einer Eigenschaft, die genau alleWörter der Sprache haben.(auch Beschreibung unendlicher Sprachen möglich)Beispiele: {w ∈ {a}∗ | |w | ≤ 3},{w ∈ {a, b}∗ | w1 = b ∧ ∀i ≥ 2 : wi = a},{w ∈ {a, b}∗ | ∀i ≥ 2 : wi = w1}

später in dieser LV noch mehr Formalismen zur endlichenBeschreibung von eingeschränkten Sprachklassen(reguläre Ausdrücke, Grammatiken, Automaten, . . . )

23

Operationen auf WörternOperationen auf Wörtern u, v ∈ A∗:Verkettung ◦ : A∗ × A∗ → A∗, wobei

∀u ∈ A∗ ∀v ∈ A∗ ∀i ∈ {1, . . . , |u|+ |v |} :

(u ◦ v)i =

{ui falls i ≤ |u|vi−|u| sonst

Beispiel: anne ◦marie = annemarieassoziativ, nicht kommutativ, ε ist neutralDamit ist (A∗, ◦, ε) ein Monoid.

Spiegelung R : A∗ → A∗, wobei

∀u ∈ A∗ ∀i ∈ {1, . . . , |u|} : uRi = u|u|+1−i

Beispiel: marieR = eiram, annaR = annau ∈ A∗ heißt Palindrom gdw. uR = u

FaktI Für jedes Wort u ∈ A∗ gilt

(uR)R

= u.I Für je zwei beliebige Wörter u, v ∈ A∗ gilt (u ◦ v)R = vR ◦ uR .

24

Anwendung: Java-StandardbibliothekRotieren einer Liste in java.util.Collections:x0, . . . , xmid−1︸ ︷︷ ︸

u

, xmid, . . . , xsize︸ ︷︷ ︸v

durch v ◦ u = (uR ◦ vR)R

private static void rotate2(List<?> list, int distance) {int size = list.size();if (size == 0)return;int mid = -distance % size;if (mid < 0)mid += size;if (mid == 0)return;

reverse(list.subList(0, mid));reverse(list.subList(mid, size));reverse(list);

}

25

Relationen auf Wörtern

Präfix v (Anfangswort):

∀u ∈ A∗ ∀v ∈ A∗ : ((u v v) ↔ (∃w ∈ A∗ (u ◦ w = v)))

z.B. tom v tomate (mit w = ate)

Postfix (Suffix):

∀u ∈ A∗ ∀v ∈ A∗ : (u Postfix von v ↔ (∃w ∈ A∗ (w ◦ u = v)))

z.B. enten ist Postfix von studenten (mit w = stud)

Infix (Faktor, zusammenhängendes Teilwort):

∀u ∈ A∗ ∀v ∈ A∗ : (u Infix von v ↔ (∃w ∈ A∗ ∃w ′ ∈ A∗ : (w ◦ u ◦ w ′ = v)))

z.B. oma ist Infix von tomate (mit w = t und w ′ = te)

26

Mehr Relationen auf WörternOrdnungen bei gegebener Reihenfolge < auf dem Alphabet A:lexikographisch Ordnung auf A∗:

∀u, v ∈ A∗ : u ≤lex v gdw.1. u v v oder2. ∃w ∈ A∗ ∃a, b ∈ A : a < b ∧ wa v u ∧ wb v v

quasi-lexikographische Ordnung auf A∗:∀u, v ∈ A∗ : u ≤qlex v gdw.1. |u| ≤ |v | oder2. |u| = |v | ∧ u ≤lex v

Beispiele: für A = {a, b} mit a < b

I ab v aba, ab ≤lex aba, ab ≤qlex aba

I abab 6v abba, aber abab ≤lex abba und abab ≤qlex abba,I aaa ≤lex ab, aber aaa 6≤qlex ab

I ab 6≤lex aaba, aber ab ≤qlex aaba

27

Sprachen als MengenSprachen L ⊆ A∗ sind Mengen von WörternEigenschaften: leer, endlich, abzählbar, überabzählbarMengenrelationen auf Sprachen:

L ⊆ L′ gdw. ∀w ∈ A∗ : w ∈ L→ w ∈ L′ giltL = L′ gdw. ∀w ∈ A∗ : w ∈ L↔ w ∈ L′ gilt

Mengenoperationen auf Sprachen:

L ∪ L′ = {w | w ∈ L ∨ w ∈ L′}L ∩ L′ = {w | w ∈ L ∧ w ∈ L′}L \ L′ = {w | w ∈ L ∧ w 6∈ L′}L∆L′ = (L \ L′) ∪ (L′ \ L)

Komplement einer Sprache L ⊆ A∗: L = A∗ \ LBeispiel:

L =⋃

n∈3N

An L =⋃

n∈{3i+1|i∈N}

An ∪⋃

n∈{3i+2|i∈N}

An

28

Weitere Operationen auf Sprachen

Verkettung ◦ von Sprachen:

L1 ◦ L2 = {u ◦ v | u ∈ L1 ∧ v ∈ L2}

Beispiel:

L1 = {111, 1, 10} L2 = {00, 0}L1 ◦ L2 = {111, 1, 10} ◦ {00, 0}

= {1110, 11100, 10, 100, 1000}

Spiegelung LR = {wR | w ∈ L}

Beispiel: L = {a, ab, aba, abab}LR = {a, ba, aba, baba}

29

Iterierte VerkettungI für Sprachen L ⊆ A∗

L0 = {ε} ∀n ∈ N : Ln+1 = Ln ◦ L = L ◦ · · · ◦ L︸ ︷︷ ︸n+1−mal

L∗ =⋃n∈N

Ln L+ =⋃

n∈N\{0}

Ln

I für Wörter u ∈ A∗:

un = u · · · u︸ ︷︷ ︸n−mal

∈ A∗, u∗ = {u}∗ = {un | n ∈ N} ⊆ A∗

u+ = u∗ \ {ε} = {u}+ = {un | n ∈ N \ {0}} ⊆ A∗

Beispiele:

(101)3 = 101101101 und 1013 = 10111a∗ = {ai | i ∈ N} = {ε, a, aa, aaa, . . .}

(ab)∗ = {(ab)i | i ∈ N} = {ε, ab, abab, ababab, . . .}

30

Reguläre Ausdrücke – Syntax

Die Menge RegExp(A) aller regulären Ausdrücke über einemAlphabet A ist (induktiv) definiert durch:IA ∅ ∈ RegExp(A),

ε ∈ RegExp(A) undfür jedes Symbol a ∈ A gilt a ∈ RegExp(A)

IS für alle E ∈ RegExp(A) und F ∈ RegExp(A) gilt(E + F ),EF , (E )∗ ∈ RegExp(A).

Beispiele: ε+ a, ε+ ∅, (a + ∅)∗, ε+ ((ab)∗a)∗

dieselbe Definition kürzer: RegExp(A) = Term(ΣF , ∅)für die SignaturΣF = {(∅, 0), (ε, 0), (∗, 1), (+, 2), (·, 2)} ∪ {(a, 0) | a ∈ A}(Baumdarstellung)

31

Beispiele(ohne überflüssige Klammern)

I Für A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} gilt0+(1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)∗

∈ RegExp(A)I Für A = {0, 1} gilt

I (1 + ε)∗ + (10)∗ ∈ RegExp(A)I (0 + 11)∗ + ((0 + (1)∗)0)∗ ∈ RegExp(A)

Oft werden

A

E+ = EE ∗

En = E · · ·E︸ ︷︷ ︸n−mal

En∗ =

E · · ·E︸ ︷︷ ︸n−mal

∗für n ∈ N als Kurzbezeichnungen verwendet.

32

Reguläre Ausdrücke – Semantik

Jeder reguläre Ausdruck E ∈ RegExp(A) repräsentiert eine SpracheL(E ) ⊆ A∗.

L(∅) = ∅L(ε) = {ε}

∀a ∈ A : L(a) = {a}∀E ,F ∈ RegExp(A) : L(E + F ) = L(E ) ∪ L(F )∀E ,F ∈ RegExp(A) : L(EF ) = L(E ) ◦ L(F )∀E ,F ∈ RegExp(A) : L(E∗) = (L(E ))∗

Eine Sprache L ⊆ A∗ heißt genau dann regulär, wenn ein regulärerAusdruck E ∈ RegExp(A) mit L = L(E ) existiert.

Beispiel: Die Menge L aller Dezimaldarstellungen natürlicher Zahlen istregulär wegen L = L (0 + (1 + 2 + · · ·+ 9)(0 + 1 + · · ·+ 9)∗)

33

Beispiele

Für A = {a, b} gilt

L(ab∗) = {a, ab, abb, abbb, abbbb, . . .} = {abi | i ∈ N}L((ab)∗) = {ε, ab, abab, ababab, . . .} = {(ab)i | i ∈ N}

L((a + b)∗) = {a, b}∗

L(a∗b∗) = {u ◦ v | u ∈ a∗ ∧ v ∈ b∗}L((a∗b∗)∗) = {a, b}∗

L((a + b)∗aba) = {u ◦ aba | u ∈ A∗}∗

Reguläre Ausdrücke ermöglichen eine endliche Darstellungunendlicher Sprachen.

34

Äquivalenz regulärer Ausdrücke

Zwei reguläre Ausdrücke E ,F ∈ RegExp(A) heißen genau dannäquivalent, wenn L(E ) = L(F ) gilt.

Beispiele:I (a + b)∗, (a∗ + b∗)∗ und a∗(ba∗)∗ sind äquivalentI ab∗ und (ab)∗ sind nicht äquivalentI (11 + 0 + 110 + 011)∗ und (11 + 0)∗ sind . . .

FaktDie Äquivalenz regulärer Ausdrücke ist eine Äquivalenzrelation.

35

Was bisher geschahAlphabet, Wort, SpracheWörter w ∈ A∗

I Operationen: Spiegelung R , Verkettung ◦I PalindromeI Relationen: Präfix, Infix, Postfix,

lexikographische, quasi-lexikographische Ordnung

Sprachen L ⊆ A∗ (L ∈ 2(A∗))

I Relationen: Mengenrelationen ⊆,=I Operationen: Mengenoperationen ∪,∩, , \

Verkettung ◦, iterierte Verkettung ∗, Spiegelung R

Reguläre AusdrückeI endliche Darstellung evtl. unendlicher SprachenI Syntax: RegExp(A) = Term(ΣF , ∅) (Baumstruktur) für

ΣF = {(∅, 0), (ε, 0), ( ∗, 1), (·, 2), (+, 2)} ∪ {(a, 0)|a ∈ A}I Semantik des regulären Ausdrucks E ∈ RegExp(A):

Sprache L(E ) ⊆ A∗

36

Interessante Fragen für SprachenI Ist ein gegebenes Wort w in der Sprache L enthalten?

(heißt oft Wortproblem)I Enthält die Sprache L nur endlich viele Wörter?I Gilt L1 ⊆ L2 für zwei gegebene Sprachen L1 und L2?I Gilt L1 = L2 für zwei gegebene Sprachen L1 und L2?

Fragen zur Regularität:

I Lässt sich die Sprache L durch einen regulären Ausdruck definieren?(Gilt ∃E ∈ RegExp(A) : L = L(E ) ?)

I Woran erkennt man, ob sich eine Sprache durch einen regulärenAusdruck definieren lässt?

I Gilt L(E ) = ∅ für einen gegebenen regulären Ausdruck E?I Gilt L(E ) = A∗ für einen gegebenen regulären Ausdruck E?I Ist ein gegebenes Wort w in der durch den regulären Ausdruck E

definierten Sprache L(E ) enthalten?

Alle Antworten sind für endliche Sprachen einfach,aber für unendliche Sprachen meist schwierig.

37

Wortersetzungssysteme

Alphabet A

Wortersetzungsregel (l , r) ∈ A∗ × A∗ (geschrieben l → r)Wortersetzungssystem endliche Menge von Wortersetzungsregeln

Beispiele:I Regel ba→ ab,I Wortersetzungssystem S = {a→ ab, ba→ c , abc → ε}

38

Anwendung von Wortersetzungsregeln

Eine Regel l → r ist auf ein Wort w ∈ A∗ anwendbar,falls l ein Infix von w ist.

Beispiel: Regel ma→ ε istI auf tomate anwendbar, u = to, v = te,I auf am, motte und meta nicht anwendbar.

Eine Anwendung der Regel l → r auf ein Wortw = u ◦ l ◦ v ∈ ergibt das Wort u ◦ r ◦ v .(Ersetzung des Teilwortes l durch r)

Beispiel: ab → a angewendet auf baababa = u ◦ l ◦ vI mit u = ba und v = aba ergibt baaabaI mit u = baab und v = a ergibt baabaa

39

Ableitungsschritt

Ableitungsschritt (u, (l → r), p, v) im Wortersetzungssystem S mitI Ausgangswort u,I auf u anwendbare Regel l → r aus S ,I Position p ∈ {1, . . . , |u|} im Wort u, an der das Teilwort l

beginntI v ist das nach Anwendung der Regel l → r an Position p auf u

entstandene Wort.

Beispiel:S = {ab → ba, a→ b}, u = abamögliche Ableitungsschritte in S(aba, (ab → ba), 1, baa)(aba, (a→ b), 3, abb)(aba, (a→ b), 1, bba)

40

Ein-Schritt-Ableitungsrelation

Jedes Wortersetzungssystem S ⊆ A∗ × A∗ definiert eine Relation→S ⊆ A∗ × A∗, wobei genau dannu →S v gilt, wenn ein Ableitungsschritt (u, (l → r), p, v) mit(l → r) ∈ S existiert.

Beispiel: Für S = {ab → ba, a→ b} giltI aba→S baa wegen (aba, (ab → ba), 1, bba)

I aba→S bba wegen (aba, (a→ b), 1, bba)

I aba→S abb wegen (aba, (a→ b), 3, abb)

I aba 6→S bbb

41

Wiederholung: Hüllen binärer RelationenR ∪ IM heißt reflexive Hülle von R ⊆ M2

(mit Identität IM = {(x , x) | x ∈ M})

R ∪ R−1 heißt symmetrische Hülle von R ⊆ M2

(mit inverser Relation R−1 = {(y , x) | (x , y) ∈ R})

Wiederholung: Verkettung ◦ der Relationen R ⊆ M2 und S ⊆ M2

R ◦ S = {(x , z) ∈ M2 | ∃y ∈ M : (x , y) ∈ R ∧ (y , z) ∈ S}

Iterierte Verkettung von R ⊆ M2 mit sich selbst:

R0 = IM

Rn+1 = Rn ◦ RR+ =

⋃n∈N\{0}

Rn ⊆ M2 transitive Hülle

R∗ =⋃n∈N

Rn ⊆ M2 reflexiv-transitive Hülle

42

Ableitungen

Eine Folge von Ableitungsschritten

(u, (l1 → r1), p1, u2), (u2, (l2 → r2), p2, u3), · · · , (un−1, (ln−1 → rn−1, pn−1, v)

im Wortersetzungssystem S heißt Ableitung von u nach v in S .

Beispiel: S = {ab → ba, a→ b}, u = abaFolge von Ableitungsschritten(aba, (ab → ba), 1, baa), (baa, (a→ b), 3, bab), (bab, (a→ b), 2, bbb)

abaab→ba−→ baa

a→b−→ baba→b−→ bbb

Länge der Ableitung = Anzahl der Ableitungsschritte

In jedem System S existiert für jedes u ∈ A∗ die leere Ableitung(der Länge 0) von u nach u.

43

Beispiele

S1 = {||| → |} mit u = ||||||| und v = ||||Was wird hier „berechnet“?Anderes Wortersetzungssystem mit derselben Wirkung?

S2 = {11→ 1, 00→ 1, 01→ 0, 10→ 0} und u = 1101001Wirkung verschiedener Ableitungreihenfolgen?

S3 = {c → aca, c → bcb, c → a, c → b, c → ε} und u = cMenge aller in S3 ableitbaren Wörter, die kein c enthalten?

44

Ersetzungsrelation

Jedes Wortersetzungssystem S ⊆ (A∗ × A∗) definiert dieErsetzungsrelation →∗S ⊆ (A∗ × A∗), wobei genau dannu →∗S v gilt, wenn eine Ableitung von u nach v existiert.

Beispiel: S = {a→ aa},I für jedes n ≥ 1 gilt ba→∗S b a · · · a︸ ︷︷ ︸

nwegen ba→S baa→S baaa→S · · · →S b a · · · a︸ ︷︷ ︸

n

I b →∗S b, aber für kein Wort w 6= b gilt b →∗S w

(→∗S ist die reflexive transitive Hülle von →S)

45

Modellierungsbeispiel: lineares SolitaireStartkonfiguration : n Spielsteine auf n benachbarten Spielfeldern.

Spielzug : Springe mit einem Stein über einen benachbarten Steinauf das nächste freie Feld und entferne denübersprungenen Stein.

Spielende , wenn kein Zug mehr möglich ist.

Modellierung als Wortersetzungssystem:I Konfiguration: w ∈ {◦, •}∗ (• - Stein, ◦ - leer, 2 - Rand)I Startkonfiguration: 2 •n 2

I zulässige Spielzüge: ◦ • • → •◦ ◦, • • ◦ → ◦◦ •, 2 • •2→ 2 •2, . . .

Fragen:I Welche Konfigurationen / Endkonfigurationen sind von der

Startkonfiguration erreichbar?I Wieviele Züge sind mindestens / höchstens notwendig, um eine

Endkonfiguration zu erreichen?

Jedes Paar (Wortersetzungssystem, Anfangskonfiguration) definiert dieMenge (Sprache) aller erreichbaren Konfigurationen.

46

Sprachen aus WortersetzungssystemenJedes Paar (Wortersetzungssystem S , Anfangswort w) über einemAlphabet A definiert die Sprache

L(S ,w) = {v ∈ A∗ | w →∗S v}

(alle Wörter v , die von w durch eine Ableitung in S erreichtwerden)B: S = {c → aca, c → bcb, c → ε}, w = cL(S ,w) = {w ◦ c ◦ wR} (Menge aller Palindrome über {a, b, c},die höchstens an der mittleren Position ein c enthalten)Jedes Paar (Wortersetzungssystem S , Menge M von Wörtern) übereinem Alphabet A definiert die Sprache

L(S ,M) =⋃w∈L

L(S ,w)

(alle Wörter v , die von irgendeinem w ∈ M durch eine Ableitung inS erreicht werden)

47

Ausdrucksstärke von Wortersetzungssystemen

WortersetzungssystemeI ermöglichen eine endliche Darstellung unendlicher Sprachen.

(als Erzeugungsvorschrift für alle Wörter der Sprache)Beispiele: L ({ε→ aaa}, ε) = {a3n | n ∈ N} = (aaa)∗

L ({2→ 020, 2→ 121}, 2) = {w2wR | w ∈ {0, 1}∗}

I können zur Modellierung von Zuständen und Übergängendazwischen verwendet werdenz.B. Spiele, Ausführung von Programmen,ProgrammverifikationBeispiel: Lineares Solitaire

I können Berechnungen simulieren(Bestimmung von erreichbaren Wörtern ohne Nachfolger)Beispiel: ε ∈ L ({||| → |}, ||||||)

48

Wortproblem für durch Wortersetzungssysteme definierteSprachen

Ist ein gegebenes Wort w in der Sprache L(S , u) enthalten?

alternative Formulierung: Gilt u →∗S w?

Ableitungsrelation →S als(unendlicher) gerichteter Graph GS = (V ,E ) mitKnoten: V = A∗

Kanten: E = {(u, v) | u →S v}

u →∗S w gilt genau dann, wenn in GS ein Pfad von u nach wexistiert.

Beispiel: (Tafel) S = {ab → ba},abab →∗S baba, aber abab 6→∗S abaa, abab 6→∗S aabb

49

Sprachen aus Wortersetzungssystemen

Lösung des Wortproblems und anderer Fragen zu Sprachen ist fürendliche Sprachen einfach, für unendliche Sprachen oft nicht.

Darstellung der Sprache durch ein Wortersetzungssystem kannhelfen.

Lösung des Wortproblem w ∈ L(S , u) durch Standardverfahren:Suche eines Pfades von u nach w im Ableitungsgraphen desWortersetzungssystems S

Problem:I Pfadsuche ist Standardverfahren für endliche Graphen.I Ableitungsgraphen von Wortersetzungssystemen sind meist

unendlich.

Standardverfahren anwendbar, wenn Suche in einem endlichenTeilgraphen genügt

50

Nichtverlängernde WortersetzungssystemeEin Wortersetzungssystem S heißt genau dann nichtverlängernd,wenn für jede Regel (l → r) ∈ S gilt: |l | ≥ |r |.Wortproblem (L,w):

Eingabe : Sprache L ⊆ A∗, Wort w ∈ A∗

Frage: Gilt w ∈ L?Ausgabe ja oder nein

Beispiel: S = {ab → ba, ac → a}, u = abcac , v = aacb

SatzEs gibt einen Algorithmus, welcher für für jedes nichtverlängerndeWortersetzungssystem S ⊆ A∗×A∗ und beliebige Wörter u,w ∈ A∗

das Wortproblem (L(S , u),w) in endlicher Zeit korrekt löst.

Idee:Suche im endlichen Teilgraphen aller Wörter v ∈ A∗ mit |v | ≤ |u|

51

Nichtverkürzende Wortersetzungssysteme

Ein Wortersetzungssystem S heißt genau dann nichtverkürzend,wenn für jede Regel (l → r) ∈ S gilt: |l | ≤ |r |.

Beispiel: S = {a→ ba, b → a}, u = ba, w = aaba, w ′ = abab

SatzEs gibt einen Algorithmus, welcher für für jedes nichtverkürzendeWortersetzungssystem S ⊆ A∗×A∗ und beliebige Wörter u,w ∈ A∗

das Wortproblem (L(S , u),w) in endlicher Zeit korrekt löst.

Idee: Suche im endlichen Teilgraphen aller Wörter v ∈ A∗ mit|u| ≤ |v | ≤ |w |

52

Wortersetzungssysteme mit verlängernden und verkürzendenRegeln

Beispiel:

S =

c → baaca,c → aacba,c → bbcabb,aca → d ,bcb → d ,ada → d ,bdb → d

Für Wortersetzungssysteme S mit verlängernden und verkürzendenRegeln existiert im Allgemeinen kein Algorithmus, der für beliebigeWörter u,w ∈ A∗ feststellt, ob u →∗s w gilt.

53

Was bisher geschah

I Alphabet, Wort, Sprache

I Operationen und Relationen auf Wörtern und Sprachen

I interessante Fragen für Sprachen und Wörter

Reguläre Ausdrücke

I Syntax, Semantik

I endliche Darstellung evtl. unendlicher Sprachen

Wortersetzungssysteme P ⊆ A∗ × A∗

I Wortersetzungssregel l → r mit l , r ∈ A∗

I Ableitung in P: endliche Folge von Ersetzungsschritten

I Ausdrucksstärke:

I Darstellung von (evtl. unendlichen) SprachenI Modellierung von ZustandsübergängenI Ausführen von Berechnungen

54

Wiederholung Wortersetzungssysteme

I A = {s,w},R = {ww → s, ss → s,ws → w , sw → w}(nichtverlängernd)Ist ww aus wsww ableitbar? (Gilt wsww →R ww?)L(R,wsww) ={wsww ,www ,wss, sw ,ws,w}

I A = {b, r ,w},S = {wr → rw , br → rb, bw → wb}(nichtverlängernd und nichtverkürzend)Ist wbbr aus brwb ableitbar?L(S , brwb) ={brwb, rbwb, rwbb}

I A = {a, b, c}, T = {a→ ba, b → cc}(nichtverkürzend)Ist aabbcc aus a ableitbar?L(T , a) =L ((b + cc)∗a)

55

Ableitbare Wörter über Teilalphabet

Beispiele: A = {a, b, c},

S =

c → aca,c → bcb,c → ε,c → a,c → b

L(S , c) = {u ◦ d ◦ uR | u ∈ {a, b}∗ ∧ d ∈ {a, b, c , ε}}

Menge aller Wörter in L(S , c) ∩ {a, b}∗:Palindrome über {a, b}

c ist Hilfssymbol zur Erzeugung der Palindrome

56

Natürliche Sprache

Wortersetzungssystem S enthält die Regeln:Satz → Subjekt Prädikat .Subjekt → mArtikel mSubstantivSubjekt → wArtikel wSubstantivmArtikel → DerwArtikel → DiemSubstantiv → HundwSubstantiv → SonnePrädikat → belltPrädikat → scheint

Alphabet A = {Der,Die,Hund, Sonne, scheint, bellt, .}∪{ Satz,Subjekt, Prädikat, wArtikel, mArtikel, wSubstantiv, mSubstantiv}

Ableitbare Wörter in L(S , Satz ) ohne Hilfssymbole aus der Menge {Satz,Subjekt, Prädikat, mArtikel, wArtikel, mSubstantiv, wSubstantiv}:Menge korrekter deutscher Sätze (dieser einfachen Form mitausschließlich den Worten Der, Die, Hund, Sonne, scheint, bellt).

57

Aussagenlogische Formeln

Wortersetzungssystem S enthält die RegelnFormel → VariableFormel → KonstanteFormel → ( ¬ Formel )Formel → ( Formel ∨ Formel )Formel → ( Formel ∧ Formel )Variable → pVariable → qKonstante → tKonstante → f

Alphabet A = {t, f, p, q,¬,∨,∧, (, )} ∪ { Formel,Variable, Konstante}

Formel→S (Formel ∧ Formel)→2S (Formel ∧ f)→∗S ((p ∨ (¬q)) ∧ f)

Wörter in L(S , Formel ) ∩ {t, f, p, q,¬,∨,∧, (, )}∗ :Menge AL({p, q}) aller aussagenlogischen Formeln mitAussagenvariablen aus der Menge {p, q}

58

Aussagenlogische DNF

Wortersetzungssystem S enthält die RegelnDNF → Minterm ∨ DNFDNF → MintermMinterm → Literal ∧ MintermMinterm → LiteralLiteral → ¬ VariableLiteral → VariableVariable → pVariable → q

Alphabet A = {p, q,¬,∨,∧}∪{ DNF, Minterm, Literal,Variable}

DNF→S Minterm ∨ DNF→3S p ∨ DNF→∗S p ∨ q ∧ ¬p ∨ ¬q

Wörter in L(S , Formel ) ∩ {t, f, p, q,¬,∨,∧, (, )}∗ :Menge AL({p, q}) aller disjunktiven Normalformen mitAussagenvariablen aus der Menge {p, q}

59

Dezimaldarstellung natürlicher ZahlenWortersetzungssystem S enthält die RegelnZahl → 0Zahl → 1Ziffernfolge

...Zahl → 9ZiffernfolgeZiffernfolge → 0Ziffernfolge

...Ziffernfolge → 9ZiffernfolgeZiffernfolge → ε

Alphabet {0, . . . , 9} ∪ { Zahl, Ziffernfolge }

Zahl→S 3Ziffernfolge→S 32Ziffernfolge→S 327Ziffernfolge→S 327

Wörter in L(S , Zahl ) ∩ {0, . . . , 9}∗ :Menge aller Dezimaldarstellungen natürlicher Zahlen

60

Programmiersprachen

Java-Syntax (Ausschnitt) in Backus-Naur Form (BNF)(John Backus, Peter Naur)

a→ r1|r2| . . . |rn statt mehrerer Regeln a→ r1, . . . , a→ rn::= statt → (in ASCII darstellbar)Hilfssymbole markiert durch < und >

61

Definition Grammatik

Grammatik G = (N,T ,P, S) mitNichtterminalsymbole endliche Menge N

(Hilfssymbole)Terminalsymbole endliche Menge T

(Alphabet der Sprache)Wortersetzungssystem P ⊆ (N ∪ T )+ × (N ∪ T )∗ (Produktionen)Startsymbol S ∈ N

Beispiel: G = (N,T ,P, S) mit

N = {S},T = {0, 1},

P =

{S → 0S1S → ε

}

62

Grammatiken: BeispieleI G = (N,T ,P,E ) mit N = {E ,F ,G}, T = {(, ), a,+, ·} und

P =

E → G ,E → E + G ,G → F ,G → G · F ,F → a,F → (E )

I G = (N,T ,P,S) mit N = {S ,A,B,C}, T = {a, b, c}

P =

S → aSBC ,S → aBC ,CB → BC ,aB → ab,bB → bb,bC → bc,cC → cc

63

Ableitungen in Grammatiken

Ableitung in Grammatik G = (N,T ,P, S):Ableitung im Ersetzungssystem P mit Startwort S

Beispiel: G = (N,T ,P, S) mit

N = {S ,A,B}T = {0, 1}

P =

S → 0SAS → 0AA → 1B → A

64

Durch Grammatiken definierte Sprachen

Grammatik G = (N,T ,P,S) definiert die Sprache

L(G ) = {w ∈ T ∗ | S →∗P w} = L(P, S) ∩ T ∗

Beispiel: G = (N,T ,P, S) mit

N = {S ,Z}T = {0, 1}

P =

S → 1Z ,S → 0,Z → 0Z ,Z → 1Z ,Z → ε

definiert die Sprache L(G ) = . . .

65

Äquivalenz von Grammatiken

Zwei Grammatiken G1 und G2 heißen genau dann äquivalent, wennL(G1) = L(G2) gilt.

Beispiel: G1 = (N1, {0, 1},P1,S) mit N1 = {S ,A,B} und

P1 =

S → 0SAS → 0AA → 1B → A

und G2 = (N2, {0, 1},P2, S

′) mit N2 = {S ′} und

P2 ={S ′ → 0S ′1, S ′ → 01

}sind äquivalent wegen L(G1) = L(G2) = . . .

Äquivalenz von Grammatiken ist eine Äquivalenzrelation. (ÜA)

66

Grammatiken mit ε-Regeln

ε-Regel : Grammatik-Regel der Form l → ε

Beispiele:I G1 = ({A,B}, {0, 1},P1,A) mit

P1 = {A→ 1B0,B → 1B0,B → ε}äquivalent zu G2 = ({A}, {0, 1},P2,A) mitP2 = {A→ 1A0,A→ 10}(ohne ε-Regel)

I G = ({A}, {0, 1},P,A) mit P = {A→ 1A0,A→ ε}nicht äquivalent zu einer Grammatik ohne ε-Regel

67

Chomsky-Hierarchie(Noam Chomsky)Eine Grammatik G = (N,T ,P,S) ist vom Chomsky-Typ

0 immer,1 , falls für jede Regel (l → r) ∈ P gilt: |l | ≤ |r |

(monoton, kontextsensitiv)2 , falls Typ 1 und für jede Regel (l → r) ∈ P gilt: l ∈ N

(kontextfrei)3 , falls Typ 2 und für jede Regel (l → r) ∈ P gilt:l ∈ N und r ∈ (T ∪ (T ◦ N))(regulär)

Eine Sprache L ⊆ T ∗ heißt vom (Chomsky-)Typ i füri ∈ {0, . . . , 3}, falls eine Grammatik G vom Typ i mitL \ {ε} = L(G ) existiert.Li bezeichnet die Menge aller Sprachen vom Typ i .Achtung: Nicht jede Sprache wird durch eine Grammatik erzeugt.

68

BeispieleI G = ({S}, {a, b},P, S) mit

P = {S → aSb, S → ab, S → a,S → b} ist vom Typ 2I G = ({S}, {a, b},P, S) mit

P = {S → aSb, S → a,S → b, S → ε} ist vom Typ 0I G = ({S ,A,B}, {a, b},P, S) mit

P = {S → aA,A→ aB,B → bB,B → b} ist vom Typ 3I G = ({A,B,C}, {a, b, c},P,A) mit

P =

A → aABC ,A → aBC ,CB → BC ,aB → ab,bB → bb,bC → bc,cC → cc

ist vom Typ 1definiert L(G ) = {anbncn | n ∈ N \ {0}}

69

Was bisher geschah: Formale SprachenI Alphabet, Wort, Sprache

Operationen und Relationen auf Wörtern und SprachenI reguläre Ausdrücke: Syntax, Semantik, ÄquivalenzI Wortersetzungssysteme

I Wortersetzungsregeln und -systemeI Ableitungen, AbleitungsgraphI durch Wortersetzungssysteme definierte SprachenI Wortproblem in Wortersetzungssystemen

im Allgemeinen nicht algorithmisch lösbar,aber algorithmisch lösbar für

I nichtverlängernde SystemeI nichtverkürzende Systeme

I GrammatikenI Terminal-, NichtterminalsymboleI Ableitungen in GrammatikenI durch Grammatiken definierte SprachenI Äquivalenz von GrammatikenI Chomsky-Hierarchie für Grammatiken und Sprachen

70

Wortproblem für Typ-1-Sprachen

gegeben : Grammatik G = (N,T ,P, S) vom Chomsky-Typ 1,Wort w ∈ T ∗

Frage : Gilt w ∈ L(G ) ?

SatzEs existiert ein Algorithmus, welcher für jede beliebige Eingabe(G ,w), wobei

I T ein endliches Alphabet,I w ∈ T ∗ undI G eine monotone Grammatik (Chomsky-Typ 1) über T sind

die Wahrheit der Aussage w ∈ L(G ) korrekt beantwortet.

(folgt aus entsprechendem Satz für nichtverkürzendeWortersetzungssysteme)demnächst spezielle (effizientere) Verfahren für Grammatiken vomChomsky-Typ 2 und 3

71

Dyck-SpracheKlammerpaar ( und )

Dyck-Sprache: Menge aller korrekt geklammerten Ausdrückeerzeugt durch Grammatik

G = ({S}, {(, )},P,S) mit

P =

S → εS → SSS → (S)

Beispiele:

I ()(()()) ∈ L(G )

I ())(6∈ L(G )

I ε ∈ L(G )

Achtung:I G hat Chomsky-Typ 0I Dyck-Sprache hat Chomsky-Typ 2

72

Allgemeine Dyck-Sprachen

Menge aller korrekt geklammerten Ausdrückemit n Paaren von Klammern: (i , )i für i ∈ {1, . . . , n}erzeugt durch Grammatik

G = ({S}, {(i , )i | i ∈ {1, . . . , n}},P, S) mit

P =

{S → εS → SS

}∪ {S → (iS)i | i ∈ {1, . . . , n}}

Symbole müssen nicht notwendig Klammern sein, z.B.aacdacababdbbcabdb ∈ Dyck-Sprache mita statt (1, b statt )1, c statt (2 und d statt )2

73

Beispiel HTML

mehrere Paare öffnender und schließender Klammern (Tags)

<html><head>

<title>Theoretische Informatik

</title></head><body>

<h1>Theoretische Informatik

</h1>...

</body></html>

74

Wiederholung: abzählbare Mengen

(Mathematik 1. Semester)

Eine Menge M heißt genau dann abzählbar, wenn sie höchstens somächtig wie N ist.(also eine surjektive Funktion f : N→ M existiert)

Mit dem ersten Diagonalverfahren von Cantor lässt sich z.B. zeigen:

I Z und Q sind abzählbar.I Für jedes endliche Alphabet A ist die Menge A∗ aller Wörter

über A abzählbar.I Für jedes endliche Alphabet A ist jede Sprache L ⊆ A∗

abzählbar.

Mengen, die nicht abzählbar sind, heißen überabzählbar.

75

Beispiele überabzählbarer MengenMit dem zweiten Diagonalverfahren von Cantor lässt sich zeigen:

R ist überabzählbar (mächtiger als N).(Es gibt überabzählbar viele reelle Zahlen.)

[0, 1] ⊂ R ist überabzählbar.(Intervall [0, 1] enthält überabzählbar viele reelle Zahlen.)

2N (Menge aller Mengen natürlicher Zahlen) ist mächtiger alsN.(Überabzählbarkeit der Menge 2N)Es gibt überabzählbar viele Mengen natürlicher Zahlen.

2{0,1}∗

Menge aller Sprachen L ⊆ {0, 1}∗ ist mächtiger als{0, 1}∗.(Es gibt überabzählbar viele Sprachen über dem Alphabet{0, 1}.)

2(A∗) ist für beliebiges endliches Alphabet A mächtiger als A∗

(Für jedes endliche Alphabet A ist die Menge allerSprachen über A überabzählbar. )

76

Lässt sich jede Sprache durch eine Grammatik erzeugen?Existiert für jedes endliche Alphabet A zu jeder Sprache L ⊆ A∗ eineGrammatik G mit L = L(G )?

Nein (Gegenbeispiel später)

Begründung:

1. Wieviele Sprachen L ⊆ A∗ gibt es? (Mächtigkeit von 2(A∗))

überabzählbar viele

2. Wieviele Grammatiken über dem endlichen Alphabet A gibt es?abzählbar viele, weil

I Alphabet A′ = A ∪ {(, ), , , {, },→, ε} endlichI Menge (A′)

∗ aller Wörter über A′ abzählbarI jede Grammatik über A ist ein Wort aus (A′)

∗

(endliche Beschreibung)I Menge aller Grammatiken über A ist Teilmenge der

abzählbaren Menge (A′)∗, also selbst abzählbar

Damit existieren sogar sehr viel mehr (überabzählbar viele) Sprachen, dienicht durch Grammatiken beschrieben werden können.

77

Zustandsübergangssystem Münzschließfach

fg

fo bo bg

b

OS

GS

Z

O

A

Aktionen: A aufschließenZ zuschließenO Tür öffnenS Tür schließenG Geld einwerfen

Zustände : fg frei, Tür zufo frei, Tür offenbo bezahlt, Tür offenbg bezahlt, Tür zub belegt

78

Endliche Automaten – Definition

NFA (nondeterministic finite automaton)A = (X ,Q, δ, I ,F ) mit

X endliches Alphabet,Q endliche Menge von Zuständen,δ Übergangsrelationen δ : X → (Q × Q),I ⊆ Q Startzustände,F ⊆ Q akzeptierende Zustände.

79

NFA: BeispielA = (X ,Q, δ, {0, 3}, {2, 3, 4}) mit

X = {a, b, c}Q = {0, 1, 2, 3, 4}

δ(a) = {(0, 0), (0, 1), (1, 3)}δ(b) = {(0, 0), (1, 2)}δ(c) = {(0, 3), (3, 3), (4, 1)}

0

3

1 2

4

a,b

c

c

a b

ca

80

Eigenschaften endlicher Automaten

NFA A = (X ,Q, δ, I ,F ) heißtvollständig , falls ∀a ∈ X∀p ∈ Q : |{q | (p, q) ∈ δ(a)}| ≥ 1

deterministisch (DFA) , falls1. |I | = 1 und2. ∀a ∈ X∀p ∈ Q : |{q | (p, q) ∈ δ(a)}| ≤ 1

Beispiele:

0 1

a,b

b

a

b

0 1

a

b

b

0 1

a

b

a

b

vollständig nicht vollständig vollständignicht deterministisch deterministisch deterministisch

81

Wiederholung: zweistellige Relationen

Verkettung der Relationen R ⊆ M ×M und S ⊆ M ×M:

R ◦ S = {(a, b) | ∃c ∈ M : (a, c) ∈ R ∧ (c , b) ∈ S}

Beispiel:

M = {a, b, c}R = {(a, a), (b, c)}S = {(a, c), (c , b)}

R ◦ S = {(a, c), (b, b)}S ◦ R = {(c , c)}

82

Darstellung als Graph

als gerichteter Graph G = (V ,E ) mit V = M und E = R

M = {a, b, c}R = {(a, a), (b, c)}S = {(a, c), (c , b)} a

b

c

Verkettung als Wege mit passender Markierung

R ◦ S = {(a, c), (b, b)}S ◦ R = {(c , c)}

a

b

c

83

Darstellung als Matrixmit Booleschen Einträgen

M = {a, b, c}

R = {(a, a), (b, c)}

1 0 00 0 10 0 0

S = {(a, c), (c , b)}

0 0 10 0 00 1 0

Verkettung als Matrixmultiplikation mit Booleschen Operationen

R ◦ S =

1 0 00 0 10 0 0

0 0 10 0 00 1 0

=

0 0 10 1 00 0 0

S ◦ R =

0 0 10 0 00 1 0

1 0 00 0 10 0 0

=

0 0 00 0 00 0 1

84

Übergangsrelation auf Wörtern

Fortsetzung der Übergangsrelationen δ : X → (Q × Q)auf Wörter δ : X ∗ → (Q × Q):

δ(ε) = {(q, q) | q ∈ Q} = IQ (Identität auf Q)δ(wa) = δ(w) ◦ δ(a)

= {(p, q) | ∃r ∈ Q : (p, r) ∈ δ(w) ∧ (r , q) ∈ δ(a)}

für alle w ∈ X ∗, a ∈ X

Für w = w1 · · ·wn ∈ X n gilt also δ(w) = δ(w1) ◦ · · · ◦ δ(wn)

(Multiplikation der Matrizen δ(w1), . . . , δ(wn))

85

Beispiel

A = ({a, b}, {0, 1}, δ, I ,F ) mitδ(a) = {(0, 0)} undδ(b) = {(0, 0), (0, 1), (1, 1)} 0 1

a,b

b

b

δ(a) =

(1 00 0

)δ(b) =

(1 10 1

)

δ(ba) = δ(b)δ(a) =

(1 10 1

)(1 00 0

)=

(1 00 0

)

δ(abb) = δ(a)δ(b)δ(b) =

(1 00 0

)(1 10 1

)(1 10 1

)=

(1 10 0

)

86

Was bisher geschah

I Alphabet, Wort, Sprache

I Operationen auf Wörtern und Sprachen

I Grammatiken, Chomsky-Hierarchie

I Wiederholung zweistellige Relationen, deren Verknüpfung undDarstellungen (Graph, Matrix)

I endlicher Automat (NFA) A = (X ,Q, δ, I ,F )

I Eigenschaften eines NFA A = (X ,Q, δ, I ,F ):

vollständig: für jedes Symbol a ∈ X und jeden Zustand p ∈ Qexistiert mindestens ein Zustand q ∈ Q mit(p, q) ∈ δ(a)

deterministisch: genau ein Startzustand undfür jedes Symbol a ∈ X und jeden Zustand p ∈ Qexistiert höchstens ein Zustand q ∈ Q mit(p, q) ∈ δ(a)

87

Wiederholung: Übergangsrelation auf Wörtern

Fortsetzung der Übergangsrelationen δ : X → (Q × Q)auf Wörter δ : X ∗ → (Q × Q):

δ(ε) = {(q, q) | q ∈ Q} = IQ (Identität auf Q)δ(wa) = δ(w) ◦ δ(a)

= {(p, q) | ∃r ∈ Q : (p, r) ∈ δ(w) ∧ (r , q) ∈ δ(a)}

für alle w ∈ X ∗, a ∈ X

Für w = w1 · · ·wn ∈ X n gilt also δ(w) = δ(w1) ◦ · · · ◦ δ(wn)

(Multiplikation der Matrizen δ(w1), . . . , δ(wn))

88

Beispiel

A = ({a, b}, {0, 1}, δ, I ,F ) mitδ(a) = {(0, 0)} undδ(b) = {(0, 0), (0, 1), (1, 1)} 0 1

a,b

b

b

δ(a) =

(1 00 0

)δ(b) =

(1 10 1

)

δ(ba) = δ(b)δ(a) =

(1 10 1

)(1 00 0

)=

(1 00 0

)

δ(abb) = δ(a)δ(b)δ(b) =

(1 00 0

)(1 10 1

)(1 10 1

)=

(1 10 0

)

89

Von einem NFA akzeptierte Wörter

NFA A = (X ,Q, δ, I ,F ) akzeptiert ein Wort w ∈ X ∗ genau dann,wenn δ(w) ∩ (I × F ) 6= ∅.

alternative Formulierung:A akzeptiert w genau dann, wenn ein akzeptierender Weg, d.h. eineFolge (q0, . . . , q|w |) von Zuständen qi ∈ Q existiert, für die gilt:1. ∀i ∈ {1, . . . , |w |} : (qi−1, qi ) ∈ δ(wi ),2. q0 ∈ I (Startzustand) und3. q|w | ∈ F (akzeptierender Zustand).

q0w1→ q1

w2→ · · · wn→ qn mit q0 ∈ I und qn ∈ F

90

BeispielA = ({a, b}, {0, 1}, δ, {0}, {0}) mit δ(a) = {(0, 1)},δ(b) = {(0, 1), (1, 0)}

0 1

a,b

b

I akzeptiert abbb über den Weg

0 a→ 1 b→ 0 b→ 1 b→ 0 ∈ F

I akzeptiert bbb nicht

0 b→ 1 b→ 0 b→ 1 6∈ F

I akzeptiert aaba nicht0 a→ 1 a→?

91

NFA-akzeptierbare Sprachen

NFA A = (X ,Q, δ, I ,F ) akzeptiert die Sprache

L(A) = {w ∈ X ∗ | ∃s ∈ I ∃f ∈ F : (s, f ) ∈ δ(w)}

Beispiel: A = ({a, b}, {0, 1, 2}, δ, {0}, {2}) mitδ(a) = {(0, 0), (2, 2)} und δ(b) = {(0, 0), (0, 1), (1, 2), (2, 2)}akzeptiert L(A) = . . .

Sprache L ⊆ X ∗ heißt genau dann NFA-akzeptierbar, wenn ein NFAA mit L = L(A) existiert.

Menge aller NFA-akzeptierbaren Sprachen: REC(NFA)(recognizable)

Beispiel: L = {w | w enthält ein Infix aa oder bba}ist NFA-akzeptierbar.

92

Beispiele NFA-akzeptierbarer Sprachen

I L1 = {w ∈ {0, 1}∗ | |w |0 ist ungerade }I L2 = {w ∈ {a, b}∗ | w beginnt mit ab und endet mit ba}I L3 = L(G ) mit G = ({S ,T}, {0, 1},P, S) mit

P = {S → 11T ,T → 0S ,T → 0}I L4 = L(E ) mit E = (a + b)∗ab∗

I L5 = L(F ) mit F = ((a + b)c)∗

93

Isomorphie endlicher AutomatenZwei NFA A = (X ,Q, δ, I ,F ) und B = (X ,Q ′, δ′, I ′,F ′) sind genaudann isomorph,wenn eine bijektive Funktion h : Q → Q ′ existiert, so daß1. genau dann s ∈ I , wenn h(s) ∈ I ′,2. genau dann f ∈ F , wenn h(f ) ∈ F ′ und3. für jedes a ∈ X :

genau dann (p, q) ∈ δ(a), wenn (h(p), h(q)) ∈ δ′(a).Beispiel: A = ({a, b}, {0, 1, 2}, δ, {0}, {0}) mitδ(a) = {(0, 1), (1, 2), (2, 0)} und δ(b) = {(0, 2), (1, 0), (2, 1)}undB = ({a, b}, {α, β, γ}, δ, {β}, {β}) mitδ(a) = {(α, β), (β, γ), (γ, α)} und δ(b) = {(α, γ), (β, α), (γ, β)}sind isomorph mit h(0) = β, h(1) = γ, h(2) = α.(Graphisomorphie zwischen gerichteten Graphen mit markiertenKanten)

FaktIsomorphie von NFA ist eine Äquivalenzrelation.

94

Äquivalenz endlicher Automaten

Zwei NFA A,B heißen genau dann äquivalent, wenn L(A) = L(B)gilt.

Beispiel: Der NFA A = ({a, b}, {0, 1, 2}, δ, {0}, {2}) mitδ(a) = {(0, 1), (1, 1)} und δ(b) = {(1, 1), (1, 2)}

und der NFA B = ({a, b}, {0, 1, 2, 3}, δ, {0}, {2}) mitδ(a) = {(0, 1), (1, 1), (2, 1), (3, 3)} undδ(b) = {(0, 3), (1, 2), (2, 2), (3, 3)}

sind äquivalent. Warum?

FaktÄquivalenz endlicher Automaten ist eine Äquivalenzrelation.

FaktIsomorphe endliche Automaten sind immer auch äquivalent.

95

Vervollständigung von NFA

Motivation:In vollständigen NFA existiert zu jedem Wort wenigstens ein Weg,Akzeptanz jedes Wortes durch Menge der mit dem letzten Symbolerreichten Zustände auf allen Wegen feststellbar.

SatzZu jedem NFA existiert ein äquivalenter vollständiger NFA.

(Hinzufügen eines zusätzlichen nichtakzeptierenden Zustandes, fallsnotwendig)

Beispiel: A = ({a, b, c}, {0, 1, 2, 3, 4}, δ, {0}, {2, 4}) mitδ(a) = {(0, 0), (1, 2), (3, 4), (4, 4)},δ(b) = {(0, 1), (0, 3)} und δ(c) = {(3, 0)}

96

Konstruktion von DFA aus NFAMotivation: In DFA existiert zu jedem Wort höchstens ein akzeptierenderWeg, schnelles Feststellen der Akzeptanz möglich.Beispiel: A = ({a, b}, {0, 1, 2, 3, 4}, δ, {0, 4}, {3}) mitδ(a) = {(0, 0), (4, 4)(0, 1), (1, 3), (3, 3)} undδ(b) = {(0, 0), (4, 4), (4, 2), (2, 3), (3, 3)}allgemeines Verfahren:

gegeben: NFA A = (X ,QA, δA, IA,FA)

gesucht: DFA B = (X ,QB , δB , IB ,FB) mit L(A) = L(B)

Potenzmengenkonstruktion: NFA B = (X ,QB , δB , IB ,FB) mit

QB = 2QA (Einschränkung auf von IB erreichbare genügt)IB = {IA}FB = {M ⊆ QA | FA ∩M 6= ∅}

∀a ∈ X : δB(a) = {(M,N) | N = {q | ∃p ∈ M : (p, q) ∈ δA(a)}}

FaktDer nach der Potenzmengenkonstruktion aus dem NFA A konstruierteAutomat B ist vollständig, deterministisch und äquivalent zu A.

97

Was bisher geschahI endlicher Automat (NFA) A = (X ,Q, δ, I ,F )

I NFA-Eigenschaften: vollständig, deterministischI akzeptierender Weg für Wort w = w1 · · ·wn in einem NFA

A = (X ,Q, δ, I ,F ):Folge (q0, . . . , qn) von Zuständen aus Q mit1. q0 ∈ I ,2. qn ∈ F und3. ∀i ∈ {1, . . . , n} : (qi−1, qi ) ∈ δ(wi )

I vom NFA A akzeptierte Sprache L(A)

I Menge aller NFA-akzeptierbaren Sprachen: REC(NFA)

I Isomorphie von NFAI Äquivalenz von NFAI Zu jedem NFA existiert ein äquivalenter vollständiger NFA.

(Vervollständigung)I Zu jedem NFA existiert ein äquivalenter DFA.

(Potenzmengenkonstruktion)98

Wiederholung: Operationen auf Sprachen

I Mengenoperationen ∪,∩, \,I Sprachoperationen R , ◦, ∗

I reguläre Ausdrücke RegExp(X ):Syntax: Menge aller Grundterme über der Signatur mit

I Konstantensymbolen ∅, ε, jedes a ∈ XI Operationssymbolen +, ∗

oder erzeugt durch Grammatik (ÜA 4.3.a)Semantik: Zuordnung

E ∈ RegExp(X ) → Sprache L(E ) ⊆ X ∗

Konstantensymbole → Basissprachen(Einermengen bzw. ∅)

Operationssymbole → Sprachoperationen

99

NFA für Spiegelung(ÜA 5.6)

Beispiel: DFA A = ({a, b}, {0, 1, 2, 3}, δA, {0}, {2, 3}) mitδA(a) = {(0, 1), (1, 3), (3, 3)} und δA(b) = {(1, 2), (2, 2)}allgemeines Verfahren:

gegeben: NFA A = (X ,Q, δA, IA,FA)

gesucht: NFA B mit L(B) = (L(A))R

Konstruktion: NFA B = (X ,Q, δB , IB ,FB) mit1. IB = FA2. FB = IA3. ∀a ∈ X : δB(a) = δA(a)−1 = {(q, p) | (p, q) ∈ δA(a)}

FaktDer oben definierte NFA B akzeptiert die Sprache (L(A))R .

Die Menge REC(NFA) ist abgeschlossen unter Spiegelung.

100

NFA für Komplement NFA-akzeptierbarer Sprachen

Beispiel:vollständiger DFA A = ({a, b}, {0, 1, 2, 3}, δ, {0}, {2}) mitδ(a) = {(0, 1), (1, 3), (2, 2), (3, 3)} undδ(b) = {(0, 3), (1, 2), (2, 2), (3, 3)}

allgemeines Verfahren:gegeben: vollständiger DFA A = (X ,Q, δ, I ,F )

gesucht: NFA B mit L(B) = L(A)

Konstruktion: DFA B = (X ,Q, δ, I ,Q \ F )

FaktDer oben definierte NFA B akzeptiert die Sprache L(A).

Die Menge REC(NFA) ist abgeschlossen unter Komplementbildung.

101

NFA für Vereinigung NFA-akzeptierbarer SprachenBeispiel: NFA A = ({a, b}, {0, 1}, δA, {0}, {0}) mitδA(a) = {(0, 1), (1, 0)} und δA(b) = ∅NFA B = ({a, b}, {2, 3, 4}, δB , {2}, {4}) mitδB(a) = {(2, 3), (4, 3)} und δB(b) = {(3, 4)}

allgemeines Verfahren:

gegeben: NFA A = (X ,QA, δA, IA,FA) undNFA B = (X ,QB , δB , IB ,FB) mit QA ∩ QB = ∅(Zustände umbenennen, falls notwendig)

gesucht: NFA C mit L(C ) = L(A) ∪ L(B)

Konstruktion: NFA C = (X ,QA ∪ QB , δC , IA ∪ IB ,FA ∪ FB) mit∀a ∈ X : δC (a) = δA(a) ∪ δB(a)

FaktDer oben definierte NFA C akzeptiert die Sprache L(A) ∪ L(B).Die Menge REC(NFA) ist abgeschlossen unter Vereinigung.Zu gegebenen NFA A und B lässt sich damit auch ein Automat C mitL(C ) = L(A) ∩ L(B) = L(A) ∪ L(B) (deMorgan) konstruieren.

102

DFA für SchnittmengeBeispiel: DFA A = ({a, b}, {0, 1}, δA, {0}, {1}) mitδA(a) = {(0, 0)} und δA(b) = {(0, 1), (1, 1)}DFA B = ({a, b}, {2, 3}, δB , {2}, {3}) mitδB(a) = {(2, 3), (3, 3)} und δB(b) = {(3, 3)}allgemeines Verfahren:

gegeben: DFA A = (X ,QA, δA, IA,FA), DFA B = (X ,QB , δB , IB ,FB)

gesucht: DFA C = (X ,QC , δC , IC ,FC ) mit L(C ) = L(A) ∩ L(B)

Produkt-Konstruktion: DFA C = (X ,QA × QB , δC , IA × IB ,FA × FB) mit∀a ∈ X : δC (a) = {((p, q), (r , s)) | (p, r) ∈ δA(a) ∧ (q, s) ∈ δB(a)}

FaktDer oben definierte DFA C akzeptiert die Sprache L(A) ∩ L(B).Die Menge REC(NFA) ist abgeschlossen unter Schnitt.Modifikation (Tafel):dieselbe Konstruktion des DFA C aus vollständigen DFA A und B

I mit akzeptierenden Zuständen FC = FA × FB

akzeptiert L(A) ∩ L(B)

I mit akzeptierenden Zuständen FC = (FA × QB) ∪ (QA × FB)akzeptiert L(A) ∪ L(B) 103

NFA mit ε-Übergängenε-NFA: NFA ohne Einschränkung δ(ε) = IQ , stattdessen δ(ε) ⊇ IQ(zusätzliche Kanten im Automatengraphen mit Beschriftung ε)

ε-NFA vereinfachen oft die Modellierung von Sprachen und Abläufen.

Beispiel:A = ({a, b, c}, {0, 1, 2}, δ, {0}, {2}) mit δ(a) = {(0, 0)}, δ(b) = {(1, 1)},δ(c) = {(2, 2)} und δ(ε) = {(0, 1), (1, 2)}Akzeptanz von Wörtern analog zu NFA:ε-NFA A = (X ,Q, δ, I ,F ) akzeptiert ein Wort w ∈ X ∗ genau dann, wennδ∗(w) ∩ (I × F ) 6= ∅.

δ∗(w) = δ∗(ε) ◦ δ(w1) ◦ δ∗(ε) ◦ · · · ◦ δ∗(ε) ◦ δ(wn) ◦ δ∗(ε)

ε-NFA A im Beispiel oben akzeptiert die Sprache L(A) = a∗b∗c∗

FaktZu jedem NFA A existiert ein äquivalenter ε-NFA B mit genau einemStartzustand und genau einem akzeptierenden Zustand.

104

Eliminierung der ε-Übergänge aus ε-NFAδ∗(ε) ist der transitive Abschluß der Relation δ(ε)ε-Hülle eines Zustandes q ∈ Q: Hε(q) = {p | (q, p) ∈ δ∗(ε)}allgemeines Verfahren:

gegeben: ε-NFA A = (X ,Q, δ, I ,F ) mit δ(ε) ⊇ IQ

gesucht: NFA B ohne ε-Übergänge mit L(B) = L(A)

Konstruktion (ε-Eliminierung): B = (X ,Q, δ′, I ′,F ) mit

I ′ =⋃q∈I

Hε(q)

∀ : a ∈ X : δ′(a) = δ(a) ∪{

(p, q′) | (p, q) ∈ δ(a) ∧ q′ ∈ Hε(q)}

FaktDer durch ε-Eliminierung aus dem ε-NFA A konstruierte NFA Benthält keine ε-Übergänge und ist äquivalent zu A.

105

NFA für Verkettung NFA-akzeptierbarer SprachenBeispiel:NFA A = ({a, b}, {0}, δA, {0}, {0}) mit δA(a) = ∅ und δA(b) = {(0, 0)}NFA B = ({a, b}, {1, 2, 3}, δB , {1, 3}, {2}) mitδB(a) = {(3, 2), (3, 3)} und δB(b) = {(1, 2)}allgemeines Verfahren:

gegeben: NFA A = (X ,QA, δA, IA,FA) undNFA B = (X ,QB , δB , IB ,FB) mit QA ∩ QB = ∅

gesucht: NFA C mit L(C ) = L(A) ◦ L(B)Konstruktion:

1. (A′ ≡ A ∧ |FA′ | = 1): ε-NFA A′ = (X ,QA ∪ {fA}, δ′A, IA, {fA}) mit∀a ∈ X : δ′A(a) = δA(a) und δ′A(ε) = δA(ε) ∪ {(q, fA) | q ∈ FA}

2. (B ′ ≡ B ∧ |IB′ | = 1): ε-NFA B ′ = (X ,QB ∪ {sB}, δ′B , {sB},FB) mit∀a ∈ X : δ′B(a) = δB(a) und δ′B(ε) = δB(ε) ∪ {(sB , q) | q ∈ IB}

3. (◦): ε-NFA C = (X ,QA ∪ QB ∪ {fA, sB}, δC , IA,FB) mit∀a ∈ X : δC (a) = δ′A(a) ∪ δ′B(a) δC (ε) = δ′A(ε) ∪ δ′B(ε) ∪ {(fA, sB)}

FaktDer oben definierte ε-NFA C akzeptiert die Sprache L(A) ◦ L(B).

Die Menge REC(NFA) ist abgeschlossen unter Verkettung.106

NFA für iterierte VerkettungBeispiel: NFA A = ({a, b}, {0, 1, 2, 3}, δA, {0}, {3}) mitδA(a) = {(0, 1), (2, 3)} und δA(b) = {(1, 2)}

allgemeines Verfahren:gegeben: NFA A = (X ,Q, δA, I ,F )gesucht: NFA B mit L(B) = L(A)∗

Konstruktion:1. (A′ ≡ A ∧ |IA′ | = 1 ∧ |FA′ | = 1):ε-NFA A′ = (X ,QA ∪ {sA, fA}, δ′A, {sA}, {fA}) mit∀a ∈ X : δ′A(a) = δA(a) undδ′A(ε) = {(sA, q) | q ∈ IA} ∪ {(q, fA) | q ∈ FA}

2. (∗): ε-NFA B = (X ,QA ∪ {sA, fA}, δB , {sA}, {fA}) mit∀a ∈ X : δB(a) = δ′A(a) undδB(ε) = δ′A(ε) ∪ {(sA, fA), (fA, sA)}

FaktDer oben definierte ε-NFA B akzeptiert die Sprache L(A)∗.Die Menge REC(NFA) ist abgeschlossen unter iterierter Verkettung.

107

Abschlusseigenschaften der Menge REC(NFA)

SatzSind L und L′ NFA-akzeptierbare Sprachen, dann sind auch dieSprachen

I L ∪ L′ (Vereinigung)I L (Komplement)I L ∩ L′ (Durchschnitt)I L ◦ L′ (Verkettung)I Ln, L∗ (iterierte Verkettung)I LR (Spiegelung)

NFA-akzeptierbar.

dieselbe Aussage kürzer:Die Menge REC(NFA) ist abgeschlossen unter

I Mengenoperationen: ∪, (und damit auch ∩ und \)I Sprachoperationen ◦, ∗, R

108

Regulärer Ausdruck → NFA

FaktJede durch einen regulären Ausdruck definierte Sprache istNFA-akzeptierbar.Beispiel: ab∗ + b

induktiver Beweis:(Induktion über die Struktur des regulären Ausdruckes)IA L(∅), L(ε) und L(a) für alle a ∈ X sind NFA-akzeptierbar

(Tafel)IS sind L(E ) und L(F ) NFA-akzeptierbar, dann sind auch

I L(E + F ) = L(E ) ∪ L(F ),I L(EF ) = L(E ) ◦ L(F ) undI L(E∗) = L(E )∗

NFA-akzeptierbar(wegen Abgeschlossenheit von REC(NFA) unter ∪, ◦, ∗)

109

Was bisher geschah

I NFA A = (X ,Q, δ, I ,F )

I Akzeptanz von Wörtern durch NFA, DFA, ε-NFAI von NFA, DFA, ε-NFA akzeptierte Sprache L(A)

I NFA-akzeptierbare Sprachen REC(NFA)I Für jede Sprache L ⊆ X ∗ sind die folgenden Aussagen

äquivalent:1. L ∈ REC(NFA), d.h. es existiert ein NFA A mit L = L(A).2. Es existiert ein vollständiger NFA B mit L = L(B).3. Es existiert ein DFA C mit L = L(C ).4. Es existiert ein vollständiger DFA D mit L = L(D).

I REC(NFA) ist abgeschlossen unter:I Mengenoperationen ∪,∩, , \I Sprachoperationen R , ◦, ∗

I Jede reguläre Sprache ist NFA-akzeptierbar.Transformation E ∈ RegExp(X ) in NFA A = (X ,Q, δ, I ,F )

110

DFA-Minimierung

Ein vollständiger DFA A heißt genau dann minimal für die SpracheL(A), wenn kein vollständiger DFA B mit L(A) = L(B) und wenigerZuständen als A existiert.

Beispiel: DFA A = ({a, b}, {0, 1, 2, 3, 4}, δ, {0}, {4}) mitδ(a) = {(0, 1), (1, 4), (2, 3), (3, 4), (4, 4)} undδ(b) = {(0, 2), (1, 2), (2, 2), (3, 0), (4, 4)}

Idee (für vollständigen DFA A = (X ,Q, δ, I ,F )):I für jedes Paar (p, q) von Zuständen in Q:

Suche nach einem (kürzesten) unterscheidenden WortI Zustände sind äquivalent, wenn kein unterscheidendes Wort

existiertI Zerlegung von Q in Äquivalenzklassen von ZuständenI diese Klassen sind die Zustände des minimalen DFA.

111

Äquivalente Zustände in einem DFA

Beispiel: A = ({a, b}, {0, 1, 2, 3}, δ, {0}, {3}) mitδ(a) = {(0, 1)} und δ(b) = {(0, 2), (1, 3), (2, 3)}

allgemein:DFA A = (X ,Q, δ, I ,F ) und Zustand q ∈ Qdefinieren einen DFA Aq = (X ,Q, δ, {q},F )

Zustände p, q ∈ Q heißen genau dann äquivalent in A, wennL(Ap) = L(Aq) gilt.

Ein Wort w ∈ X ∗ unterscheidet die Zustände p ∈ Q und q ∈ Q,falls w ∈ L(Ap)∆L(Aq) (= (L(Ap) ∪ L(Aq)) \ (L(Ap) ∩ L(Aq))).(symmetrische Differenz von L(Ap) und L(Aq))

112

Algorithmus zur Bestimmung äquivalenter Zuständegegeben: DFA A = (X ,Q, δ, I ,F )

FaktFalls das Wort w ∈ X ∗ die Zustände p′, q′ ∈ Q in A unterscheidet undfür ein a ∈ X gilt (p, p′) ∈ δ(a) und (q, q′) ∈ δ(a), dann unterscheidetdas Wort aw ∈ X ∗ die Zustände p, q ∈ Q in A.Induktive Berechnung einer Folge Ti von Mengen von unterscheidbarenZustandspaaren (Beispiel Tafel):

T0 = {{p, q} | p ∈ F , q 6∈ F}

Ti+1 = Ti ∪

{p, q} | ∃a ∈ X ∃p′, q′ ∈ Q :

{p′, q′} ∈ Ti

∧(p, p′) ∈ δ(a)∧(q, q′) ∈ δ(a)

(Ti : Menge aller durch ein w mit |w | ≤ i unterscheidbaren Paare)Alternative Darstellung: Folge von Äquivalenzrelationen ∼i ⊆ Q2 mit

p ∼i q gdw. ∀w ∈ X ∗ : |w | ≤ i → (w ∈ Ap ↔ w ∈ Aq)

Für jeden vollständigen DFA A existiert ein n ∈ N mit Tn = Tn+1.Für jedes Paar {p, q} 6∈ Tn sind p und q äquivalent in A.

113

Minimalautomatgegeben: DFA A = (X ,QA, δA, IA,FA)

Minimalautomat für L(A):DFA B = (X ,QB , δB , IB ,FB) mit

QB = {[q]A | q ∈ Q} Äquivalenzklassen in A

∀a ∈ X : δB(a) = {([p]A, [qA]) | (p, q) ∈ δA(a)}IB = {[q]A | q ∈ IA}FB = {[q]A | q ∈ FA}

SatzZu jeder NFA-akzeptierbaren Sprache L ⊆ X ∗ existiert ein (bis aufIsomorphie) eindeutiger äquivalenter vollständiger DFA A mitL = L(A) und einer minimalen Anzahl von Zuständen(Minimalautomat für L).

114

Entscheidung der Äquivalenz von NFA

Eingabe: NFA A,BAusgabe: ja, falls A und B äquivalent (also L(A) = L(B))

nein, sonst

Algorithmus:1. Konstruktion der DFA A′ und B ′ mit

L(A′) = L(A) und L(B ′) = L(B) (Potenzmengenkonstruktion),2. Konstruktion der Minimalautomaten

A′′ zu A′ und B ′′ zu B ′ (Minimierungsalgorithmus),3. Test, ob A′′ und B ′′ isomorph sind

(Isomorphietest für Graphen).

FaktDie NFA A und B sind genau dann äquivalent, wenn dieAutomaten A′′ und B ′′ isomorph sind.

115

Entscheidung der Äquivalenz regulärer Ausdrücke

Eingabe: Reguläre Ausdrücke E ,FAusgabe: ja, falls E und F äquivalent

nein, sonst

Algorithmus:

1. Bestimmung von NFA AE und AF

mit L(AE ) = L(E ) und L(AF ) = L(F ),

2. Berechnung der DFA A′E und A′F mitL(A′E ) = L(E ) und L(A′F ) = L(F ) (Potenzmengenkonstruktion),

3. Berechnung der MinimalautomatenA′′E zu A′E und A′′F zu A′F (Minimierungsalgorithmus),

4. Test, ob A′′E und A′′F isomorph sind (Isomorphietest für Graphen).

FaktDie regulären Ausdrücke E und F sind genau dann äquivalent, wenn dieAutomaten A′′E und A′′F isomorph sind.

Beispiel: (ab)+a und a(ba)∗ba116

NFA und reguläre Grammatiken

Beispiel: NFA A = ({a, b}, {0, 1, 2}, δ, {0}, {2}) mitδ(a) = {(0, 1)} und δ(b) = {(1, 0), (1, 2)}

reguläre Grammatik G = ({S ,B}, {a, b},P,S) mitP = {S → aB,B → bS ,B → b}

definieren beide die SpracheL(A) = L(G ) = {(ab)n | n ∈ N \ {0}}

SatzEine Sprache L ⊆ X ∗ ist genau dann NFA-akzeptierbar, wennL \ {ε} von einer regulären Grammatik (Chomsky-Typ 3) erzeugtwird.

117

Konstruktion: reguläre Grammatik → NFAgegeben: reguläre Grammatik G = (N,X ,P,S) (Chomsky 3)Konstruktion: NFA A = (X ,Q, δ, I ,F ) mit

Q = N ∪ {f } mit f 6∈ N

I = {S}F = {f }

für jedes a ∈ X : δ(a) = {(A,B) | (A→ aB) ∈ P}∪{(A, f ) | (A→ a) ∈ P}

Beispiel: Zur regulären Grammatik G = ({S ,B}, {0, 1},P,S) mitP = {S → 0B,B → 0B,B → 1S ,B → 0}wird der NFA A = ({0, 1}, {S ,B, f }, δ, {S}, {f }) mitδ(0) = {(S ,B), (B,B), (B, f )} und δ(1) = {(B,S)} konstruiert.FaktFür den wie oben zur Grammatik G konstruierten NFA A giltL(G ) = L(A).

118

Konstruktion: NFA → reguläre Grammatikgegeben: NFA A = (X ,Q, δ, I ,F )Konstruktion: reguläre Grammatik G = (N,X ,P, S) mit

N = Q ∪ {S} mit S 6∈ Q

P =⋃a∈X{p → aq | (p, q) ∈ δ(a)}

∪⋃a∈X{S → aq | ∃s ∈ I : (s, q) ∈ δ(a)}

∪⋃a∈X{p → a | ∃f ∈ F : (p, f ) ∈ δ(a)}

Beispiel: A = ({a, b}, {0, 1, 2}, δ, {0}, {2}) mitδ(a) = {(0, 1), (1, 2)} und δ(b) = {(1, 1), (2, 1)}konstruierte Grammatik G = ({S , 0, 1, 2}, {a, b},P, S) mitP = {0→ a1, 1→ b1, 1→ a2, 2→ b1,S → a1, 1→ a}FaktFür die wie oben aus dem NFA A konstruierte Grammatik G giltL(G ) = L(A) \ {ε}. 119

Was bisher geschahI NFA A = (X ,Q, δ, I ,F )

I vollständig (Vervollständigung)I deterministisch, DFA (Potenzmengenkonstruktion)I Minimalautomat: minimaler vollständiger DFA

I Für jede Sprache L ⊆ X ∗ sind die folgenden Aussagenäquivalent:1. L ∈ REC(NFA), d.h. es existiert ein NFA A mit L = L(A).2. Es existiert ein DFA B mit L = L(B).3. Es existiert ein eindeutiger minimaler vollständiger DFA C mit

L = L(C ).4. Es existiert eine reguläre Grammatik G mit L = L(G ).

I Automatenkonstruktionen für Operationen auf Sprachen:I Mengenoperationen ∪,∩, , \,∆I Sprachoperationen R , ◦, ∗

I Die Menge REC(NFA) aller NFA-akzektierbaren Sprachen istabgeschlossen unter

I Mengenoperationen ∪,∩, , \,∆ undI Sprachoperationen ◦, ∗, R

120

DFA → regulärer AusdruckBeispiel: A = ({a, b}, {1, 2}, δ, {1}, {1}) mitδ(a) = {(1, 2)} und δ(b) = {(1, 1)(2, 1)}gegeben: DFA A = (X ,Q, δ, I ,F ) mit Q = {1, . . . , n} und I = {1}schrittweise Konstruktion regulärer Ausdrücke(Dynamische Programmierung):

R(k , i , j) beschreibt die Menge aller Wörter, für die ein Pfadvon i zu j nur über (Zwischen-)Zustände ≤ k existiert

R(0, i , j) =

{{a ∈ X | (i , j) ∈ δ(a)} falls i 6= j

ε+ {a ∈ X | (i , j) ∈ δ(a)} falls i = j

R(k + 1, i , j) = R(k , i , j) + (R(k , i , k + 1)R(k , k + 1, k + 1)∗R(k, k + 1, j))

FaktFür den so konstruierten regulären Ausdruck E =

⋃f ∈F R(n, 1, f )

gilt L(E ) = L(A).121

NFA und reguläre Ausdrücke

Schon gezeigt:

FaktJede NFA-akzeptierbare Sprache wird durch einen regulärenAusdruck definiert.

FaktJede durch einen regulären Ausdruck definierte Sprache istNFA-akzeptierbar.

Das ergibt zusammen:

SatzEine Sprache ist genau dann NFA-akzeptierbar (∈ REC(NFA)),wenn sie regulär (durch einen regulären Ausdruck definiert) ist.REC(NFA) ist genau die Menge aller regulären Sprachen.

122

Schubfachschluss-Prinzip(Pigeonhole principle)Verteilt man mehr als n Objekte in n Schubfächer, dann gibt es(wenigstens) ein Schubfach, welches (wenigstens) zwei Objekte enthält.

∀O∀S∀f : ((|O| > |S | ∧ f : O → S)→ ∃x∃y : (x 6= y ∧ f (x) = f (y)))

Für |O| > |S | existiert keine injektive Funktion f : O → S .Beispiele:

I Von 13 Personen haben mindestens zwei im selben MonatGeburtstag.

I Wieviele Karten aus einem Skatblatt muss man ziehen, damit zweiderselben Farbe dabei sind?

I vier verschiedene Paare Socken im Dunklen:Wieviele Socken muss man (blind) nehmen, damit ein vollständigesPaar dabei ist?

123

Nicht NFA-akzeptierbare SprachenFaktDie Sprache L = {anbn | n > 0} ist nicht NFA-akzeptierbar.Beweisschema (indirekter Beweis):

L nicht NFA-akzeptierbar gdw. ¬∃A : (L(A) = L) gdw. ∀A : ¬(L(A) = L)

gdw. ∀A : ( (L(A) = L)︸ ︷︷ ︸Annahme P(A)

→ ¬(L(A) = L)︸ ︷︷ ︸Folgerung ¬P(A)

)

Beweis: Annahme: für NFA A = (X ,Q, δ, I ,F ) mit k = |Q| gilt L(A) = LWegen akbk ∈ L existiert ein akzeptierender Pfad für akbk in A:

q0a→ q1

a→ · · · a→ qkb→ qk+1

b→ · · · b→ q2k

SFS: |Q| = k (Schubfächer) und |{0, . . . , k}| > k (Objekte)Daher existieren i , j ∈ {0, . . . , k} mit i < j und qi = qj .

q0a→ q1

a→ · · · a→ qia→ qj+1

a→ · · · a→ qkb→ qk+1

b→ · · · b→ q2k

ist also akzeptierender Pfad für ak−(j−i)bk in A, d.h ak−(j−i)bk ∈ L(A)Aus ak−(j−i)bk 6∈ L folgt ¬(L(A) = L) im Widerspruch zur Annahme.Also ist die Annahme falsch und es existiert kein NFA A mit L = L(A).

124

Nicht NFA-akzeptierbare Sprache

Die Grammatik G = (N,T ,P, S) mit N = {S},T = {a, b} undP = {S → aSb, S → ab}ist kontextfrei und erzeugt die nicht NFA-akzeptierbare SpracheL(G ) = {anbn | n > 0}

Also ist nicht jede kontextfreie Sprache(Chomsky-Typ 2) NFA-akzeptierbar.

L(G ) ∈ L2 \ REC(NFA) also L2 6⊆ REC(NFA)

125

Weitere nicht NFA-akzeptierbare Sprachensehr hilfreiches Prinzip:Da REC(NFA) unter ∩ abgeschlossen ist, gilt für alleSprachen L, L′, L′′:

( L ∩ L′ = L′′ ∧ L′ ∈ REC(NFA) ∧ L′′ 6∈ REC(NFA) )→ L 6∈ REC(NFA)

I L = {w ∈ {a, b}∗ | |w |a = |w |b > 0} 6∈ REC(NFA)(wegen L ∩ a∗b∗ = {anbn | n > 0} 6∈ REC(NFA) )

I L = {w ∈ {a, b}∗ | 2|w |a = |w |b ∈ N} 6∈ REC(NFA)(wegen L ∩ a∗b∗ = {anb2n | n > 0} 6∈ REC(NFA) nachSchubfachschluss).

I L = {w ∈ {a, b}∗ | w = wR} 6∈ REC(NFA) (Palindrome)(wegen L ∩ a∗ba∗ = {anban | n ∈ N} 6∈ REC(NFA))

I L = {a(n2) | n ∈ N} 6∈ REC(NFA)(wegen Schubfachschluss, Wortlängen)

126

Anwendung von NFA und regulären Sprachen

I Modellierung vom Verhalten von Zustandsübergangssystemen,z.B.

I reale Geräte und AnlagenI Softwaresysteme

Überprüfung, ob Zustandsübergangssystem bestimmteAnforderungen erfüllt

I Beschreibung der Syntax von Programmiersprachen z.B.I endlicher Mengen (Mengen von Schlüsselwörtern)I Folgen von Zeichen und ZeichenkettenI Zahlendarstellungen

I lexikalische Analyse im CompilerI Suche nach Zeichenketten in Texten

(string matching)I Textverarbeitung, z.B. Wortvervollständigung

127

Ergebnisse über reguläre SprachenFür jede Sprache L ⊆ X ∗ sind die folgenden Aussagen äquivalent:

I L hat den Chomsky-Typ 3.I L = L(E ) für einen regulären Ausdruck E .I L ist NFA-akzeptierbar.I Es existiert ein DFA A mit L = L(A).I Es existiert eine reguläre Grammatik G mit L \ {ε} = L(G ).I Es existiert eine reguläre Grammatik G mit ε-Regel und L = L(G ).I Es existiert eine rechtslineare Grammatik Gr mit L = L(Gr ) \ {ε}.I Es existiert eine rechtslineare Grammatik G ′r mit ε-Regel mit

L = L(Gr ).I Es existiert eine linkslineare Grammatik Gl mit L = L(Gl) \ {ε}.I Es existiert eine linkslineare Grammatik G ′l mit ε-Regel mit

L = L(G ′l ).

Die Menge aller Sprachen vom Chomsky-Typ 3 ist abgeschlossen unter

I Mengenoperationen: ∪,∩, , \,∆I Sprachoperationen: ◦, ∗, R

128

Algorithmische Lösungen für reguläre Sprachenalle Sprachen in Eingaben endlich beschrieben, z.B. als NFA

Wortproblem Eingabe: (L,w),Ausgabe: ja, falls w ∈ L, sonst nein(Suche nach mit w markiertem Pfad imAutomatengraphen)

Leerheit Eingabe: L, Ausgabe: ja, falls L = ∅, sonst nein(Erreichbarkeit akzeptierender Zustände in NFA für L)

Vollständigkeit Eingabe: L, Ausgabe: ja, falls L = X ∗, sonst nein(Erreichbarkeit im Automaten für L)

(Un-)Endlichkeit Eingabe: L, Ausgabe: ja, falls L (un-)endlich, sonst nein(Suche nach akzeptierendem Weg mit Schleife)

Inklusion Eingabe: L1, L2,Ausgabe: ja, falls L1 ⊆ L2, sonst nein(Test L1 ∩ L2 = ∅)

Gleichheit Eingabe: L1, L2,Ausgabe: ja, falls L1 = L2, sonst nein(isomorphe Minimalautomaten oder Test L1∆L2

?= ∅)

Disjunktheit Eingabe: L1, L2,Ausgabe: ja, falls L1 ∩ L2 = ∅, sonst nein

129

Was bisher geschahChomsky-Hierarchie für Sprachen:L0 Menge aller durch (beliebige) Grammatiken beschriebenen

SprachenL1 Menge aller monotonen (Kontextsensitive) SprachenL2 Menge aller kontextfreien SprachenL3 = REG Menge aller regulären SprachenREG ist abgeschlossen unter ∪,∩, , ◦, ∗, R

I reguläre Ausdrücke beschreibenI reguläre Grammatiken (Chomsky-Typ 3) erzeugenI endliche Automaten akzeptieren

genau alle regulären Sprachen.einige nicht-reguläre Sprachen (mit Nachweis):{anbn | n ∈ N}, Palindromsprachen,

{a(2

n) | n ∈ N}

Anwendung z.B. beiSuche nach Zeichenketten, lexikalischer Analyse im Compiler

130

WH: Algorithmische Lösungen für reguläre Sprachenalle Sprachen in Eingaben endlich beschrieben, z.B. als NFA

Wortproblem Eingabe: (L,w),Ausgabe: ja, falls w ∈ L, sonst nein(Suche nach mit w markiertem Pfad imAutomatengraphen)

Leerheit Eingabe: L, Ausgabe: ja, falls L = ∅, sonst nein(Erreichbarkeit akzeptierender Zustände in NFA für L)

Vollständigkeit Eingabe: L, Ausgabe: ja, falls L = X ∗, sonst nein(Erreichbarkeit im Automaten für L)

Endlichkeit Eingabe: L, Ausgabe: ja, falls L endlich, sonst nein(Suche nach akzeptierendem Weg mit Schleife)

Inklusion Eingabe: L1, L2,Ausgabe: ja, falls L1 ⊆ L2, sonst nein(Test L1 ∩ L2 = ∅)

Gleichheit Eingabe: L1, L2,Ausgabe: ja, falls L1 = L2, sonst nein(isomorphe Minimalautomaten oder Test L1∆L2

?= ∅)

Disjunktheit Eingabe: L1, L2,Ausgabe: ja, falls L1 ∩ L2 = ∅, sonst nein

131

Analoge Fragen für kontextfreie Sprachen

Wiederholung:Eine Sprache L ⊆ X ∗ heißt genau dann kontextfrei, wenn für einekontextfreie Grammatik (Chomsky-Typ 2) G gilt L \ {ε} = L(G ).

CF: Menge aller kontextfreien Sprachen

Unter welchen der Operationen ∪,∩, , ◦, ∗, R ist die Menge CFabgeschlossen?

Gibt es ein passendes Maschinenmodell für kontextfreie Sprachen?

Wie zeigt man, dass eine Sprache nicht kontextfrei ist?

Gibt es algorithmische Lösungen für die folgenden Probleme fürkontextfreie Sprachen:

I WortproblemI Leerheit, Vollständigkeit, EndlichkeitI Inklusion, Gleichheit, Disjunktheit

132

Kontextfreie Grammatiken – Wiederholung

Grammatik G = (N,T ,P,S) vom Chomsky-Typ 2

Alle Regeln in P haben die Form l → r mitl ∈ N und r ∈ (N ∪ T )+

Grammatik G = (N,T ,P,S) erzeugt die Sprache

L(G ) = {w ∈ T ∗ | S →∗P w}

I Syntax regulärer (arithmetischer, logischer) AusdrückeI Syntax von Programmiersprachen

(zusammengesetzte Ausdrücke und Anweisungen)

133

Ableitungsbäume für kontextfreie GrammatikenBeispiel: Grammatik G = (N,T ,P,E ) mit N = {E ,F},T = {a, b, c, (, ),+, ∗},

P = {E → (E + E ),E → F ∗ F ,F → E ,E → a,E → b,E → c}

Ableitung für w = (c ∗ a + (b + a ∗ a))

allgemein: Grammatik G = (N,T ,P, S)Ableitung S →P w1 →P w2 →P · · · →P wn = w für w in G

Ableitungsbaum zu einem Wort w in der kontextfreien GrammatikG (induktive Definition):

I Wurzel mit Markierung S

I für jeder Anwendung einer Regel A→P r1 · · · rn :Verzweigung bei Symbol A in n Kinder mit Markierungenr1 . . . , rn

I Markierung der Blätter (von links nach rechts): Wort w

Ein Ableitungsbaum repräsentiert i.A. mehrere Ableitungen.134

Rechts- und Linksableitungen

Eine Ableitung für w in G heißtLinksableitung , falls in jedem Schritt das am weitesten links

stehende NichtterminalRechtsableitung , falls in jedem Schritt das am weitesten rechts

stehende Nichtterminalersetzt wird.

Zu jedem Ableitungsbaum für w in G existierenI genau eine Linksableitung für w in G undI genau eine Rechtsableitung für w in G .

135

Mehrdeutige kontextfreie GrammatikenGrammatik G heißt

eindeutig , falls für jedes Wort w ∈ L(G ) genau einAbleitungsbaum in G existiert.

mehrdeutig , sonst.

Beispiel: Grammatik G = (N,T ,P,E ) mit N = {S}, T = {a} undP = {S → SS ,S → a}für w = aaa

Eindeutigkeit von Grammatiken ist wichtig beim Entwurf vonProgrammiersprachen (Syntax)

„dangling else“-Problem:

<Anw> ::= if <Ausdr> then <Anw><Anw> ::= if <Ausdr> then <Anw> else <Anw>

Was bedeutet:if C1 then if C2 then A else B

136

Inhärent mehrdeutige Sprachen

Sprachen L, für die keine eindeutige Grammatik G mit L = L(G )existieren, heißen inhärent mehrdeutig.

FaktDie Sprache L = {albmcn | l ,m, n > 0 ∧ (l = m ∨m = n)}ist inhärent mehrdeutig.

137

Abschlusseigenschaften von CFSatzSind L1 und L2 kontextfreie Sprachen, dann sind auch

I L1 ∪ L2

I L1 ◦ L2

I L∗1

kontextfreie Sprachen.Konstruktionen (Tafel):gegeben: Li = L(Gi ) mit Gi = (Ni ,Ti ,Pi ,Si ) für i ∈ {1, 2}, wobeiN1 ∩ N2 = ∅ (falls nötig, umbenennen)neues Nichtterminal S ′ 6∈ N1 ∪ N2

I L1 ∪ L2 = L(G∪) mitG∪ = (N1 ∪ N2 ∪ {S ′},T1 ∪ T2,P1 ∪ P2 ∪ {S ′ → S1,S

′ → S2},S ′)I L1 ◦ L2 = L(G◦) mit

G◦ = (N1 ∪ N2 ∪ {S ′},T1 ∪ T2,P1 ∪ P2 ∪ {S ′ → S1S2},S ′)I L∗1 = L(G∗) mit

G∗ = (N1 ∪ {S ′},T1,P1 ∪ {S ′ → ε, S ′ → S1S′},S ′)

138

Erreichbare und erzeugende Nichtterminale

kontextfreie Grammatik G = (N,T ,P,S)

Nichtterminal A ∈ N heißterreichbar aus B ∈ N, falls

∃u, v ∈ (N ∪ T )∗ : B →∗P uAv

erreichbar in G falls A aus Startsymbol S erreichbar isterzeugend falls ∃w ∈ T ∗ : A→∗P w

Beispiel:Grammatik G = (N,T ,P,S) mit N = {S ,A,B,C ,D,E},T = {a, b, c},

P = {S → AB,A→ C ,A→ a,D → ScA,B → b,C → BbC}

139

Eliminierung nutzloser Nichtterminalegegeben: kontextfreie Grammatik G = (N,T ,P, S)

induktive Bestimmung aller erzeugenden Nichtterminale aus N:

M0 = {A | (A→ w) ∈ P ∧ w ∈ T ∗}Mi+1 = Mi ∪ {A | (A→ w) ∈ P ∧ w ∈ (T ∪Mi )

∗}

Es gibt ein n ∈ N : Mn = Mn+1, Mn enthält alle erzeugenden NTEliminierung aller nicht-erzeugenden NT:Löschen aller Regeln, die nicht-erzeugende NT enthalten

induktive Bestimmung aller aus S erreichbaren Nichtterminale:

M ′0 = {S}M ′i+1 = M ′i ∪ {A | (B → uAv) ∈ P ∧ B ∈ M ′i ∧ u, v ∈ (N ∪ T )∗}

Es gibt ein n ∈ N : M ′n = M ′n+1, M′n enthält alle erreichbaren NT

Eliminierung aller nicht-erreichbaren NT:Löschen aller Regeln, die nicht-erreichbare NT enthalten

140

Reduzierte kontextfreie Grammatiken

reduzierte Grammatik enthält nur erreichbare und erzeugendeNichtterminale

FaktZu jeder kontextfreien Grammatik existiert eine äquivalentereduzierte Grammatik.

Erzeugung einer reduzierten Grammatik aus beliebiger kontextfreierGrammatik G :

nacheinander in dieser Reihenfolge:1. G ′ entsteht durch Eliminierung aller nicht-erzeugenden

Nichtterminale in G ,2. G ′′ entsteht durch Eliminierung aller nicht-erreichbaren

Nichtterminale in G ′

G ′′ ist reduziert und äquivalent zu G .

141

Kettenregeln

Kettenregel Regel l → r mit l ∈ N und r ∈ N

Beispiel: G = ({A,B,S}, {0, 1},P,S) mitP = {S → 0S0, S → 00,S → A,A→ 1A,A→ B,B → 1}Eliminierung der Kettenregeln aus G = (N,T ,P, S):

I induktive Bestimmung aller Ketten-Paare

M0 = {(A,A) | A ∈ N}Mi+1 = Mi ∪ {(A,C ) | (A,B) ∈ Mi ∧ (B → C ) ∈ P}

Es existiert ein n ∈ N mit Mn = Mn+1.I P ′ = {A→ w | (A,B) ∈ Mn ∧ (B → w) ∈ P ∧ w 6∈ N}

I Hinzufügen aller Nicht-Kettenregeln A→ w , für welche P eineRegel B → w enthält und (A,B) ∈ Mn (Ketten-Paar)

I Löschen aller Kettenregeln

Die so erzeugte Grammatik G ′ ist äquivalent zu G .142

Chomsky-NormalformKontextfreie Grammatiken G = (N,T ,P, S) mit∀(l → r) ∈ P : r ∈ (N2 ∪ T ) heißen in Chomsky-Normalform.(binäre Ableitungsbäume)

SatzZu jeder kontextfreien Grammatik G mit ε 6∈ L(G ) existiert eineäquivalente Grammatik in Chomsky-Normalform.Konstruktion:1. ε-Regeln und Kettenregeln eliminieren2. N ′ = N ∪ {Xc | c ∈ T}

P ′ = P ∪ {Xc → c | c ∈ T}Ersetzung jedes Terminals c in jeder rechten Regelseite r mit|r | > 1 durch Xc

3. Ersetzung jeder Regel A→ B1 . . .Bn in P ′ mit n > 2 durch diefolgenden n − 1 Regeln:A→ B1C2, . . . ,Ci → BiCi+1, . . . ,Cn−1 → Bn−1Bn mit neuenNichtterminalen Ci

143

Was bisher geschahREG: Menge aller regulären Sprachen (Chomsky-Typ 3)

I abgeschlossen unter ∪,∩, , ◦, ∗, R

I Wortproblem algorithmisch entscheidbar(Suche im Automaten-Graphen)

I Beschreibung durchI reguläre GrammatikenI NFA (Maschinenmodell)I reguläre Ausdrücke

I prominente nicht-reguläre Sprachen (Nachweis):{anbn | n ∈ N}, Palindromsprachen,

{a(2

n) | n ∈ N}

CF: Menge aller kontextfreien Sprachen (Chomsky-Typ 2)I abgeschlossen unter ∪, ◦, ∗, R

auch unter ∩, ?I Algorithmus zur Lösung des Wortproblems ?I Maschinenmodell ?I nicht-kontextfreie Sprachen (Nachweis) ?

144

Wortproblem für kontextfreie Sprachen

Eingabe: kontextfreie Grammatik G = (N,T ,P,S)(in Chomsky-Normalform)Wort w = w1 . . .wn ∈ T ∗

Ausgabe: ja, falls w ∈ L(G ), sonst nein

Beispiel: G = ({S ,A,B}, {a, b, c},P,S) mit

P = {S → SA,S → a,A→ BS ,B → BB,B → BS ,B → b,B → c}

abc 6∈ L(G ), abacba ∈ L(G ),

Idee:I für jedes Teilwort wi . . .wj Suche nach Nichtterminal, welches

wi . . .wj erzeugt,I Beginn bei Teilworten der Länge 1I alle Zerlegungen von wi . . .wj in zwei Teilworte testen

145

CYK-Algorithmus

(Cocke, Younger, Kasami)

löst Wortproblem für kontextfreie Sprachen in O(|w |3)

induktive Berechnung der Mengen Ni,j = {A ∈ N | A→∗P wi . . .wj}durch die Rekursionsgleichung:

Ni,j =

{{A | A→ wi ∈ P} falls i = j⋃

i≤k≤j−1{A | A→ BC ∈ P ∧ B ∈ Ni,k ∧ C ∈ Nk+1,j} falls i < j

dynamische Programmierung: Tabelle (Tafel)

Faktw ∈ L(G ) gilt genau dann, wenn S ∈ N1,|w | gilt.

146

Nicht-kontextfreie Sprachen

Die Grammatik G = ({A,B,C}, {a, b, c},P,A) mit

P =

A → aABC ,A → aBC ,CB → BC ,aB → ab,bB → bb,bC → bc,cC → cc

erzeugt die Sprache L(G ) = {anbncn | n > 0}.(Chomsky-Typ 1, kontextsensitiv)

FaktDie Sprache L = {anbncn | n > 0} ist nicht kontextfrei.

147

Pumping-Lemma für kontextfreie SprachenSprache L ⊆ X ∗ hat die Pump-Eigenschaft gdw.∃ n ∈ N ∀ w ∈ L (|w | ≥ n→

∃ u, v , x , y , z ∈ X ∗ (w = uvxyz ∧ |vxy | ≤ n ∧ |vy | ≥ 1→∀ i ∈ N : uv ixy iz ∈ L

))n heißt hier Pumping-Konstante.

Satz (Pumping-Lemma für CF)Jede kontextfreie Sprache hat die Pump-Eigenschaft.

Ausführlichere Formulierung desselben Satzes:

Satz (Pumping-Lemma für CF)Für jede kontextfreie Sprache Lexistiert eine Zahl n ∈ N (Pumping-Konstante), so dassfür jedes Wort w ∈ L mit |w | ≥ neine Zerlegung w = uvxyz existiert mitu, v , x , y , z ∈ X ∗, |vy | ≥ 1, |vxy | ≤ n undfür jede Zahl i ∈ N gilt uv ixy iz ∈ L.

148

Beispiele nicht-kontextfreier Sprachen

I {anbncn | n ∈ N}I {anbmanbm | m, n ∈ N}I {w ∈ {a, b, c}∗ | |w |a = |w |b = |w |c}I {ww | w ∈ {a, b}∗}I {a(2k) | k ∈ N}

Das Pumping-Lemma ist geeignet, um zu zeigen, dass eine Sprachenicht kontextfrei ist.

ABER:Es gibt nicht-kontextfreie Sprachen mit Pump-Eigenschaft,z.B. L = {ajbkc ldm | j = 0 ∨ k = l = m}

149

Abschlusseigenschaften von CF

schon gezeigt:Sind L1 und L2 kontextfreie Sprachen, dann sind auch

I L1 ∪ L2

I L1 ◦ L2

I L∗1kontextfreie Sprachen.

Die Menge aller kontextfreien Sprachen ist nicht abgeschlossenunter

I Schnitt ∩,Gegenbeispiel:L1 = {aibick | i , k > 0} ∈ CF undL2 = {aibkck | i , k > 0} ∈ CF,aber L1 ∩ L2 = {aibic i | i > 0} 6∈ CF

I Komplement (Warum ?)

150

Was bisher geschahreguläre Sprachen:

I endliche Repräsentation durchI reguläre GrammatikenI NFA (DFA, ε-NFA, . . . )I reguläre Ausdrücke

I abgeschlossen unter ∪,∩, , ◦, ∗, R

I algorithmische Entscheidbarkeit von

Wortproblem w?∈ L (O(|w |)),

Leerheit, Endlichkeit, Gleichheit usw.

kontextfreie Sprachen:I repräsentiert durch

I kontextfreie Grammatiken (reduziert, Chomsky-NF)

I abgeschlossen unter ∪, ◦, ∗aber nicht abgeschlossen unter ∩,

I Wortproblem algorithmisch entscheidbar (CYK, O(|w |3))

151

MaschinenmodelleDefinition (endliche Beschreibung) durch

I interne Steuerung(z.B. endliche Menge von Zuständen)

I externen Speicher mit speziellenZugriffsmöglichkeiten

I Typ des Speicherinhaltes(z.B. endliches Wort über endlichem Alphabet)

I Zugriffsmethode (z.B. Lesen / Schreiben,einmal / wiederholt, feste Reihenfolge)

Konfigurationen (Momentaufnahmen)und endliche Menge zulässiger lokaler Übergänge zwischenKonfigurationen

schrittweise Berechnung : Folge von Konfigurationen von einerStartkonfiguration über zulässige Konfigurationsübergänge

Akzeptanz einer Eingabe durch akzeptierende Berechnung:endliche Konfigurationenfolge zu einer akzeptierendenKonfiguration

152

Definition des Maschinenmodells NFA

algorithmische Lösung des Wortproblems w ∈ L für reguläreSprachen L (gegeben durch NFA A mit L = L(A))

NFA A = (X ,Q, δ, I ,F ) als abstrakte Maschine:externer Speicher Eingabeband aus einzelnen linear angeordneten

Speicherzellen (enthält ein Wort w ∈ X ∗, jede Zelleein Symbol aus dem Alphabet )

interner Speicher enthält Zustand aus QSteuerelement Zugriff auf

I Eingabeband (externer Speicher): LesenBewegung in jedem Schritt eine Zelle nach rechts

I Zustand (interner Speicher): Lesen undSchreiben

153

Arbeitsweise des Maschinenmodells NFA

Start Steuerelement (Lesekopf) in einem Startzustandüber der ersten Zelle des Eingabewortes

Schritt I NFA liest Zeichen in der Zelle unter demLesekopf

I Zustandsübergang im Steuerelement(entsprechend Übergangsrelation und gelesenemSymbol)

I Lesekopf bewegt sich zur rechten NachbarzelleEnde Lesekopf auf Zelle ohne Eingabesymbol

NFA akzeptiert das Eingabewort,falls akzeptierender Zustand im internen Speicher

154

Konfigurationen eines NFANFA A = (X ,Q, δ, I ,F )

Konfiguration (q,w) mitaktuellem Zustand q ∈ Q undungelesenem Teil des Eingabewortes w ∈ X ∗

Startkonfiguration (s, u) mitStartzustand s ∈ I und Eingabewort u ∈ X ∗

Akzeptierende Konfiguration (f , ε) mit akzeptierendem Zustand f ∈ F

Folgekonfiguration zur Konfiguration (p, aw) mit a ∈ X und w ∈ X ∗:Konfiguration (q,w) mit (p, q) ∈ δ(a)Notation: (p, aw) ` (q,w)

Berechnung für Eingabewort w ∈ X ∗ in A:Folge ((q0, u0), . . . , (qn, un)) von Konfigurationen, wobeifür alle i ∈ {0, . . . , n − 1} gilt (qi , ui ) ` (qi+1, ui+1)

akzeptierende Berechnung für Eingabewort w ∈ X ∗ in A:Berechnung für w mit Endkonfiguration (qn, vn) = (f , ε)(analog zu akzeptierendem Pfad für w in A)

155

BeispielA = ({a, b}, {0, 1, 2}, δ, {0}, {2}) mitδ(a) = {(0, 0), (1, 2)} und δ(b) = {(0, 1), (2, 2)}

0 1 2

a

ab

b

Eingabewort aababStartkonfiguration (0, aabab)Endkonfiguration (2, ε)akzeptierende Berechnung für Eingabewort aabab in A:

(0, aabab) ` (0, abab) ` (0, bab) ` (1, ab) ` (2, b) ` (2, ε)

Man bemerke die Analogie zum akzeptierenden Pfad

0 a→ 0 a→ 0 b→ 1 a→ 2 b→ 2

für aabab in A156

Maschinenmodelle und AlgorithmenI endliche BeschreibungI schrittweise BearbeitungI (Ergebnis nach endlich vielen Schritten)

Jede abstrakte Maschine führt einen Algorithmus aus.(z.B. zur Lösung des Wortproblems (L,w) für reguläre Sprachen L)verschiedene Maschinenmodelle unterscheiden sich in

I Art und Kapazität des internen und externen SpeichersI Art des Zugriffs auf internen und externen SpeicherI Reihenfolge der Zugriffe (einmalig, wiederholt)I Determinismus

Maschinen definieren Sprachen:Menge aller Eingaben mit akzeptierenden Berechnungen

Maschinenmodelle definieren Sprachklassen:Menge aller durch eine solche Maschine definiertenSprachen

157

Kellerautomaten – Motivation

L = {wcwR | w ∈ {a, b}∗} ist kontextfrei, aber nicht regulär (nichtNFA-akzeptierbar).

gesucht:(einfaches) Maschinenmodell, welches die Sprache L akzeptiert

Maschine benötigt Speicher für Reihenfolge der Symbole in w , umauf diese in umgekehrter Reihenfolge zugreifen zu können (LIFO)

geeignete Datenstruktur für Speicher mit dieser Eigenschaft:Stack (Keller)

Kellerautomat (pushdown automaton, PDA):Erweiterung von NFA (mit ε-Übergängen)um internen Speicher (vom Typ Keller, Stack)

158

Kellerautomaten (PDA) – Definition

nichtdeterministischer Kellerautomat (PDA)A = (X ,Q, Γ, δ, q0,F ,⊥) mit

X Alphabet (endlich, nichtleer)Q Menge von Zuständen (endlich, nichtleer)Γ Kelleralphabet (endlich, nichtleer)q0 ∈ Q StartzustandF ⊆ Q Menge der akzeptierenden Zuständeδ : (X ∪ {ε})→ (Q × Q × Γ× Γ∗)Übergangsrelationen mit Änderung des Kellerinhaltes

⊥ ∈ Γ Kellerboden-Symbol

159

PDA – Beispiel

PDA A = ({a, b, c}, {q0, p, q}, {⊥,A,B}, δ, q0, {q},⊥) mitδ(a) = {(q0, q0,K ,AK ), (p, p,A, ε)} mit K ∈ {⊥,A,B}δ(b) = {(q0, q0,K ,BK ), (p, p,B, ε)} mit K ∈ {⊥,A,B}δ(c) = {(q0, p,K ,K )} mit K ∈ {⊥,A,B}δ(ε) = {(p, q,⊥,⊥)}

q0 p q

a : K | AKb : K | BK

c : K | K

a : A | εb : B | ε

ε : ⊥ | ⊥

mit K ∈ {⊥,A,B}

160

PDA – KonfigurationenKonfiguration (q,w , k) ∈ Q × X ∗ × Γ∗ mit

I Zustand q ∈ Q

I (noch zu lesendes) Eingabewort w ∈ X ∗

I Kellerinhalt k ∈ Γ∗

I Startkonfigurationen (q0,w ,⊥) mit w ∈ X ∗ beliebig

I Übergang zwischen Konfigurationen:(p, aw ,Gk) ` (q,w , k ′k) mit (p, q,G , k ′) ∈ δ(a) für k ∈ Γ∗

und (p,w ,Gk) ` (q,w , k ′k) mit (p, q,G , k ′) ∈ δ(ε) für k ∈ Γ∗

I akzeptierende Konfigurationen (q, ε, k) mit q ∈ F , k ∈ Γ∗

akzeptierende Berechnung (Konfigurationenfolge) für w in A:Folge (q0,w0, k0) ` · · · ` (qn,wn, kn) von Konfigurationen mit

I (q0,w0, k0) eine Startkonfiguration mit w0 = w

I (qn,wn, kn) eine akzeptierende Konfiguration mit wn = ε

I für jedes i ∈ {1, . . . , n} gilt (qi−1,wi−1, ki−1) ` (qi ,wi , ki )

161

Von PDA akzeptierte Sprachen

PDA A = (X ,Q, Γ, δ, q0,F ,⊥) akzeptiert das Wort w ∈ X ∗ gdw.eine akzeptierende Berechnung (Konfigurationenfolge) mit derStartkonfiguration (q0,w ,⊥) existiert.

PDA A = (X ,Q, Γ, δ, q0,F ,⊥) akzeptiert die Sprache

L(A) = {w ∈ X ∗ | A akzeptiert w}

Sprache L heißt PDA-akzeptierbar gdw. ein PDA A mit L = L(A)existiert.

PDA A und B heißen äquivalent gdw. L(A) = L(B)

162

PDA-Akzeptanz – BeispielPDA A = ({a, b}, {q0, p, q}, {⊥, x}, δ, q0, {q},⊥) mitδ(a) = {(q0, q0,K , xK )} für K ∈ {x ,⊥}δ(b) = {(p, p, x , ε)}δ(ε) = {(q0, p,K ,K ), (p, q,⊥,⊥)} mit K ∈ {x ,⊥}

q0 p q

a : K | xK

ε : K | K

b : x | ε

ε : ⊥ | ⊥

für K ∈ {x ,⊥}A akzeptiert das Wort aabb über die Konfigurationenfolge

(q0, aabb,⊥) ` (q0, abb, x⊥) ` (q0, bb, xx⊥) ` (p, bb, xx⊥)

` (p, b, x⊥) ` (p, ε,⊥) ` (q, ε,⊥)

und ε über die Konfigurationenfolge (q0, ε,⊥) ` (p, ε,⊥) ` (q, ε,⊥)aber nicht abb, abaEs gilt L(A) = {anbn | n ∈ N}Damit ist die Sprache {anbn | n ∈ N} PDA-akzeptierbar.

163

Deterministische PDA

PDA A = (X ,Q, Γ, δ, q0,F ,⊥) heißt deterministisch (DPDA) gdw.

∀a ∈ X ∀q ∈ Q ∀K ∈ Γ : |{(p,B) | (q, p,K ,B) ∈ δ(a)∪ δ(ε)}| ≤ 1

Sprache L heißt deterministisch kontextfrei gdw. eindeterministischer PDA A mit L = L(A) existiert.

Beispiele:I L = {anbn | n ∈ N} ist deterministisch kontextfrei,I L′ = {wcwR ∈ {a, b}∗ | w ∈ {a, b}∗} ist deterministisch

kontextfrei,I L′′ = {wawR ∈ {a, b}∗ | w ∈ {a, b}∗} nicht.

Die Menge aller durch deterministische PDA akzeptierbarenSprachen ist eine echte Teilmenge der Menge aller durch PDAakzeptierbaren Sprachen.

164

PDA – Akzeptanz durch leeren Kelleralternative Akzeptanzbedingungakzeptierende Konfigurationen: (q, ε, ε) mit q ∈ Q beliebigAngabe akzeptierender Zustände überflüssigBeispiel: L = {anbn | n ∈ N} ist PDA-akzeptierbar durchPDA A = ({a, b}, {q0, p}, {⊥, x}, δ, q0,⊥) mitδ(a) = {(q0, q0,K , xK )} für K ∈ Γδ(b) = {(p, p, x , ε)}δ(ε) = {(q0, p,K ,K ), (q0, p,⊥, ε), (p, p,⊥, ε)} für K ∈ {x ,⊥}

q0 p

a : K | xKε : K | Kε : ⊥ | ε

b : x | εε : ⊥ | ε

für K ∈ {x ,⊥}165

Akzeptanzbedingungen für PDAzwei Möglichkeiten zur Definition akzeptierender Konfigurationen:

1. Akzeptanz durch akzeptierenden Zustand (analog NFA):(q, ε, k) mit q ∈ F und k ∈ Γ∗ beliebig

2. Akzeptanz durch leeren Keller:(q, ε, ε) mit q ∈ Q beliebig

Beispiel: Die Sprache L = {anbn | n ∈ N} wird

durch akzeptierende Zustände ak-zeptiert durch den PDA A =({a, b}, {q0, p, q}, {⊥, x}, δ, q0, {q},⊥)mit

q0 p q

a : K | xK

ε : K | K

b : x | ε

ε : ⊥ | ⊥

mit leerem Keller akzep-tiert durch den PDA B =({a, b}, {q0, p, q}, {⊥, x}, δ, q0,⊥)mit

q0 p

a : K | xKε : K | Kε : ⊥ | ε

b : x | εε : ⊥ | ε

für K ∈ {x ,⊥}

166

Äquivalenz beider AkzeptanzbedingungenSatz

1. Zu jedem PDA mit akzeptierenden Zuständen existiert einäquivalenter PDA, der mit leerem Keller akzeptiert.

2. Zu jedem PDA, der mit leerem Keller akzeptiert, existiert einäquivalenter PDA mit akzeptierenden Zuständen.

Idee (PDA-Transformationen):

1. PDA mit akzeptierenden Zuständen → PDA mit leerem Keller:neues Kellerboden-Symbol und neuen Endzustand hinzufügen,ursprünglicher Automat arbeitet „darüber“,nach Übergang in einen akzeptierenden Zustand ε-Übergänge indiesem akzeptierenden Zustand zum Entfernen aller restlichenKellersymbole

2. PDA mit leerem Keller → PDA mit akzeptierenden Zuständen:neuen (einzigen) akzeptierenden Zustand hinzufügen,für jeden Übergang in eine Konfiguration mit leerem Keller einenÜbergang in diesen akzeptierenden Zustand hinzufügen.

167

Was bisher geschah

reguläre Sprachen:I endliche Repräsentation durch

I reguläre GrammatikenI NFA (DFA, ε-NFA, . . . )I reguläre Ausdrücke

I abgeschlossen unter ∪,∩, , ◦, ∗, R

I algorithmische Entscheidbarkeit vonWortproblem, Leerheit, Endlichkeit, Gleichheit usw.

kontextfreie Sprachen:I repräsentiert durch

I kontextfreie Grammatiken (reduziert, Chomsky-NF)

I abgeschlossen unter ∪, ◦, ∗aber nicht abgeschlossen unter ∩,

I Wortproblem algorithmisch entscheidbar (CYK, O(n3))

168

Unendliche Konfigurationsfolgen

Automaten mit ε-Übergängen erlauben unendlicheKonfigurationsfolgen.

Beispiele:I ε-NFA A = ({a}, {0, 1}, δA, {0}, {1}) mitδA(a) = {(0, 1)}, δA(ε) = {(0, 0), (1, 0)}

I PDA B = ({a}, {0, 1}, {⊥,X}, δB , {0}, {0},⊥) mitδA(a) = {(0, 1,⊥,⊥), (0, 1,X ,X )},δA(ε) = {(0, 1,⊥,X⊥), (1, 0,X , ε)}

Akzeptierende Konfigurationsfolgen für endliche Wörter sind immerendlich.

Deshalb sind unendliche Konfigurationsfolgen für die Definition vonSprachen und Sprachklassen endlicher Wörter durch endlicheAutomaten irrelevant.

169

Schnitt PDA-akzeptierbarer mit regulären SprachenSatz

I Sind L eine PDA-akzeptierbare und L′ eine reguläre Sprache, dannist die Sprache L ∩ L′ PDA-akzeptierbarer.

I Sind L eine durch einen DPDA-akzeptierbare und L′ eine reguläreSprache, dann ist die Sprache L ∩ L′ durch einen DPDAakzeptierbarer.

gegeben: PDA A = (X ,QA, Γ, δA, iA,FA,⊥) mit L = L(A)(akzeptiert mit Zuständen)DFA B = (X ,QB , δB , iB ,FB) mit L′ = L(B)

Beispiel: Dyck-Sprache ∩ a∗b∗ = {anbn | n ∈ N}Produktkonstruktion:PDA C = (X ,QA × QB , Γ, δ, (iA, iB),FA × Fb,⊥) mit

∀a ∈ X : δ(a) =

{((pA, pB), (qA, qB),G , k) | (pA, qA,G , k) ∈ δA(a)

∧(pB , qB) ∈ δB(a)

}δ(ε) = {((pA, pB), (qA, pB),G , k) | (pA, qA,G , k) ∈ δA(ε)}

Für den oben konstruierten PDA C gilt L(C ) = L(A) ∩ L(B).

170

Kontextfreie Grammatiken und PDA

SatzDie Menge aller kontextfreien (d.h. durch eine kontextfreieGrammatik erzeugten) Sprachen ist genau die Menge allerPDA-akzeptierbaren Sprachen.

1. Konstruktion eines PDA A zu einer gegebenen kontextfreienGrammatik G mit L(A) = L(G )

2. Konstruktion einer kontextfreien Grammatik G zu einemgegebenen PDA A mit L(A) = L(G )

(Konstruktionen auf den folgenden Folien,2. im WS2015/16 nicht besprochen)

171

Kontextfreie Grammatik → PDABeispiel: Łukasiewicz-Sprache erzeugt durch die GrammatikG = ({S}, {a, b},P,S) mit P = {S → a,S → bSS}LemmaZu jeder kontextfreien Grammatik G existiert ein PDA A mitL(A) = L(G ).gegeben: kontextfreie Grammatik G = (N,X ,P,S)Idee: Tiefensuche im Ableitungsbaum (Linksableitung)PDA A = (X , {q},N ∪ X , δ, q,S) mit

δ(ε) = {(q, q,B,w) | B → w ∈ P}∀a ∈ X : δ(a) = {(q, q, a, ε)}

akzeptiert mit leerem KellerFür den so konstruierten PDA A gilt L(A) = L(G ).Nachweis: Eindeutige Zuordnung zwischen Linksableitungen

S → u1A1v1 → u1u2A2v

2 → · · · → u1 . . . um−1Am−1vm−1 → w = u1 . . . um

und akzeptierenden Berechnungen für w = u1 . . . um

(q,w ,S) ` (q, u1 . . . um, u1A1v1) ` · · · ` (q, u2 . . . um,A1v

1)

` (q, u2 . . . um, u2A2v2) ` · · · ` (q, um, um) ` · · · ` (q, ε, ε)

172

PDA → kontextfreie Grammatik

Beispiel: PDA A = ({a, b}, {q}, {X ,⊥}, δ, q,⊥} (LK-Akzeptanz)mit δ(a) = {(q, q,X ,XX )(q, q,⊥,X⊥)},δ(b) = {(q, q,X , ε)} und δ(ε) = {(q, q,⊥, ε)}

LemmaZu jedem PDA A existiert eine kontextfreie Grammatik G mitL(A) = L(G ).

Nacheinanderausführung der KonstruktionenPDA → kontextfreie Grammatik → PDAführt zur folgenden Aussage:

FolgerungZu jedem PDA existiert ein äquivalenter PDA mit einem Zustand,der mit leerem Keller akzeptiert.

173

PDA → kontextfreie Grammatik (Vorbereitung)FaktJeder PDA A = (X ,Q, Γ, δ, q0,⊥) (LK-Akzeptanz) ist äquivalentzu einem PDA B = (X ,Q ′, Γ′, δ′, q′0,⊥′) (LK-Akzeptanz) mit derEigenschaft

∀a ∈ X ∪ {ε} ∀(p, q,G ,w) ∈ δ′(a) : |w | ≤ 2

Konstruktion: für jedes a ∈ x ∪ {ε}Ersetzung jedes Überganges (p, q,G ,w) ∈ δ(a) für w = w1 . . .wn

mit n > 2 durch die Regeln

(p, p1,G ,wn−1wn) ∈ δ(a)

(p1, p2,wn−1,wn−2wn−1) ∈ δ(ε)...(pn−1, q,w2,w1w2) ∈ δ(ε)

mit neu hinzugefügten Zuständen p1, . . . , pn−1174

PDA → kontextfreie Grammatik (Idee)gegeben: PDA A = (X ,Q, Γ, δ, q0,⊥) (LK-Akzeptanz) mit∀a ∈ X ∪ {ε} ∀(p, q,G ,w) ∈ δ(a) : |w | ≤ 2Ziel: Konstruktion einer kontextfreien Grammatik G = (N,X ,P,S), sodass die Linksableitungen in G genau den akzeptierenden Berechnungenin A entsprechen.akzeptierende Berechnung für w in A:

(q0,w ,⊥) ` · · · ` (q, ε, ε)

mögliche Konfigurationsübergänge in A:

I oberes Kellersymbol löschen (p, q,A, ε) ∈ δ(a) für a ∈ X ∪ {ε}entspricht Grammatikregel (p,A, q)→ a

I oberes Kellersymbol durch genau ein neues ersetzen(p, q,A,B) ∈ δ(a) für a ∈ x ∪ {ε}entspricht Grammatikregel (p,A, q′)→ a(q,B, q′) für alle q′ ∈ Q

I oberes Kellersymbol durch genau zwei neue ersetzen(p, q,A,BC ) ∈ δ(a) für a ∈ x ∪ {ε}entspricht Grammatikregel (p,A, q′)→ a(q,B, r)(r ,C , q′) für alleq′, r ∈ Q

175

PDA → kontextfreie Grammatik (Konstruktion)

gegeben: PDA A = (X ,Q, Γ, δ, q0,⊥) (LK-Akzeptanz) mit∀a ∈ X ∪ {ε} ∀(p, q,G ,w) ∈ δ(a) : |w | ≤ 2

Konstruktion kontextfreier Grammatik G = (N,X ,P,S) mit

N = (Q × Γ× Q) ∪ {S}P = {S → (q0,⊥, q) | q ∈ Q}

∪ {(p,B, q)→ a | (p, q,B, ε) ∈ δ(a)}∪ {(p,B, q)→ a(p′,C , q) | (p, p′,B,C ) ∈ δ(a) ∧ q ∈ Q}∪ {(p,B, q)→ a(p′,C , q)(q,D, q′) | (p, p′,B,CD) ∈ δ(a) ∧ q, q′ ∈ Q}

Für die so konstruierte Grammatik G gilt L(A) = L(G ).

176

PDA → kontextfreie Grammatik (Beispiel)

PDA A = ({a, b}, {q}, {X ,⊥}, δ, q,⊥} (LK-Akzeptanz) mitδ(a) = {(q, q,X ,XX )(q, q,⊥,X⊥)},δ(b) = {(q, q,X , ε)}, δ(ε) = {(q, q,⊥, ε)}

G = (N,X ,P, S) zu A mit

N = {S , (q,⊥, q), (q,X , q)}

P =

S → (q,⊥, q)(q,X , q)→ b wegen (q, q,X , ε) ∈ δ(b)(q,⊥, q)→ ε wegen (q, q,⊥, ε) ∈ δ(ε)(q,X , q)→ a(q,X , q)(q,X , q) wegen (q, q,X ,XX ) ∈ δ(a)(q,⊥, q)→ a(q,X , q)(q,⊥, q) wegen (q, q,⊥,X⊥) ∈ δ(a)

177

Zusammenfassung kontextfreie Sprachen (CF)CF = L2 (Chomsky-Typ 2)

Abschlusseigenschaften:Sind L1 und L2 kontextfreie Sprachen, dann sind auch

I L1 ∪ L2

I L1 ◦ L2

I L∗1I L1 ∩ L′ für jede reguläre Sprache L′

kontextfreie Sprachen.

Die Menge aller kontextfreien Sprachen ist nicht unter Schnitt undKomplement abgeschlossen.

passendes Maschinenmodell: PDA

deterministische PDA akzeptierenI eine echte Teilmenge aller kontextfreien SprachenI eine echte Teilmenge aller regulären Sprachen

178

CF: Algorithmische Lösungenalgorithmisch lösbar sind

I Wortproblem: Eingabe (G ,w)Ausgabe: ja, falls w ∈ L(G ), sonst nein(CYK-Algorithmus)

I Leerheit: Eingabe G ,Ausgabe: ja, falls L(G ) = ∅, sonst nein(ja, falls Startsymbol der Grammatik nicht erzeugend, Reduktion)

I Endlichkeit: Eingabe G ,Ausgabe: ja, falls L(G ) endlich, sonst nein(Gilt ∃w ∈ L : n ≤ |w | < 2n für Pumping-Konstante n ?)

nicht algorithmisch entscheidbar sind (ohne Nachweis)I Inklusion ⊆: Eingabe G1,G2,

Ausgabe: ja, falls L(G1) ⊆ L(G2), sonst neinI Gleichheit =: Eingabe G1,G2,

Ausgabe: ja, falls L(G1) = L(G2), sonst neinI Disjunktheit: Eingabe G1,G2,

Ausgabe: ja, falls L(G1) ∩ L(G2) = ∅, sonst neinI Kontextfreiheit der Schnittsprache: Eingabe G1,G2,

Ausgabe: ja, falls L(G1) ∩ L(G2) kontextfrei, sonst nein179

REG und CF: Anwendung (Wiederholung)

Übersetzung von Quell- in Zielsprache(z.B. C, Java in Maschinen- oder Byte-Code)

meist in zwei Phasen über eine (gemeinsame) Abstraktion:

Quellcode↓ Analyse-Phase (Front-End)

Zwischendarstellung(oft Baumstruktur)

↓ Synthese-Phase (Back-End)Code in Zielsprache

180

Analyse-PhaseQuellcode Scanner Folge von Token Parser Syntaxbaum

lexikalische Analyse (Scanner): lineare Analyse des Quelltextes,Aufteilung in Einheiten (Token), z.B. Schlüsselwörter,Bezeichner, Zahlenreguläre Sprachen, endliche Automaten

Syntaxnalyse (Parser): hierarchische Struktur des Quelltextesz.B. Ausdrücke, Verzweigungen, Schleifenkontextfreie Sprachen, Kellerautomaten

I Konstruktion des Syntaxbaumes (top-down oderbottom-up) beim Durchlaufen des Eingabewortes

I für deterministisch kontextfreie Sprachen miteindeutigen Grammatiken existieren schnelleVerfahren als CYK

I Automatische Erzeugung von Parsern ausGrammatiken durch Parsergeneratoren

semantische Analyse Annotationen im Syntaxbaum, z.B. Typprüfungen

mehr dazu in den LV Compilerbau, Prinzipien von Programmiersprachen181

Kontextsensitive SprachenLi (Chomsky-Typ 1)erzeugt durch Grammatiken G = (N,T ,P,S) mit Regeln der Forml → r , wobei

I l ∈ (N ∪ T )+

I r ∈ (N ∪ T )∗ undI |l | ≤ |r | (nichtverkürzend, monoton)

Beispiel: {anbncn | n > 0} istI nicht kontextfrei (Pumping-Lemma)I durch Grammatik G = ({A,B,C}, {a, b, c},P,A) mit

P =

A → aABC ,A → aBC ,CB → BC ,aB → ab,bB → bb,bC → bc,cC → cc

182

Wiederholung: MaschinenmodelleDefinition (endliche Beschreibung) durch

I interne Steuerung(z.B. endliche Menge von Zuständen)

I externen und internen Speicher mit speziellenZugriffsmöglichkeiten

I Typ des Speicherinhaltes(z.B. endliches Wort über endlichem Alphabet)

I Zugriffsmethode (z.B. Lesen / Schreiben,einmal / wiederholt, feste Reihenfolge)

Konfigurationen (Momentaufnahmen)und endliche Menge zulässiger lokaler Übergänge zwischenKonfigurationen

schrittweise Berechnung : Folge von Konfigurationen von einerStartkonfiguration über zulässige Konfigurationsübergänge

Akzeptanz einer Eingabe durch akzeptierende Berechnung:endliche Konfigurationenfolge zu einer akzeptierendenKonfiguration

183

Wiederholung: Sprachdefinition durch MaschinenI endliche BeschreibungI schrittweise BerechnungI Ergebnis nach endlich vielen Schritten

Jede Maschine führt einen Algorithmus aus.verschiedene Maschinenmodelle unterscheiden sich in

I Art und Kapazität des internen und externen SpeichersI Art des Zugriffs auf internen und externen SpeicherI Reihenfolge der Zugriffe (z.B. einmalig, wiederholt)I Determinismus

Jede Maschine definiert eine Sprache:Menge aller Eingaben mit akzeptierenden BerechnungenJedes Maschinenmodell definiert eine Sprachklasse:Menge aller durch eine solche Maschine definierten SprachenMaschinenmodelle zur Lösung des Wortproblems für Sprachen vomChomsky-Typ 3 (regulär): NFA, DFA, ε-NFAChomsky-Typ 2 (kontextfrei): PDAChomsky-Typ 1 (kontextsensitiv): ? 184

Linear beschränkter Automat (LBA) – IdeeZiel: Maschinenmodell für Sprachen vom Chomsky-Typ 1Definition (endliche Beschreibung) durch

I externer Speicher:1. Eingabeband aus Zellen

I Typ des Speicherinhaltes:endliches Wort über endlichem Alphabet (Eingabealphabet)

I Zugriffsmethode: LesenBewegung des Lese-Kopfes auf ein Nachbarfeld

I interner Speicher:2. endliche Menge von Zuständen (Lesen / Schreiben)3. Arbeitsband aus Zellen

I Typ des Speicherinhaltes:endliches Wort (Länge = Länge des Eingabewortes)über endlichem Alphabet (Arbeitsalphabet)

I Zugriffsmethode: Lesen / SchreibenBewegung des Lese/Schreib-Kopfes auf ein Nachbarfeld

übliche Vereinfachung der Struktur:Zusammenfassen der Bänder im internen und externen Speicher zu einemEingabe- und Arbeitsband (2,3) mit Lese/Schreib-Zugriff

185

LBA – DefinitionLinear beschränkter Automat (LBA) M = (X ,Q, Γ, δ, q0,F ,2) mit

X endliches EingabealphabetQ endliche Menge von ZuständenΓ ⊃ X endliches Arbeitsalphabetδ ⊆ (Γ× Q × Γ× Q × {L,R,N})Übergangsrelation

q0 StartzustandF akzeptierende Zustände2 ∈ Γ \ X Leere-Zelle-Symbol

(Markierung von Anfang und Ende der Eingabe)

LBA M heißt deterministisch gdw.für jedes a ∈ Γ und jedes q ∈ Q gilt

| {(a, q, b, p, x) | p ∈ Q, b ∈ Γ, x ∈ {L,R,N}} ∩ δ| ≤ 1

186

LBA – BeispielLBA M = ({a, b, c}, {q0, q1, q2, q3, f }, {a, b, x ,2}, δ, q0, {f },2) mit

δ = { (2, q0,2, f ,N)

(2, q3,2, q0,R)

(a, q0, x , q1,R)

(a, q1, a, q1,R)

(a, q3, a, q3, L)

(b, q1, x , q2,R)

(b, q2, b, q2,R)

(b, q3, b, q3, L)

(c , q2, x , q3, L)

(x , q0, x , q0,R)

(x , q1, x , q1,R)

(x , q2, x , q2,R)

(x , q3, x , q3, L)}

187

Konfigurationen eines LBA

LBA M = (X ,Q, Γ, δ, q0,F ,2)

Konfiguration uqv ∈ (Γ∗ × q × Γ∗) bedeutet:I aktueller Bandinhalt: w = uvI aktueller Zustand des LBA: qI Schreib-/Lesekopf des LBA zeigt auf erstes Symbol von v

(Leere-Zelle-Symbol, falls v = ε)

Startkonfigurationen q0w mit w ∈ X ∗

akzeptierende Konfigurationen uqv mit q ∈ FKonfigurationsübergänge von upv mit u = u′a und v = bv ′:

für (b, p, c , q,R) ∈ δ : upv ` ucqv ′

für (b, p, c , q, L) ∈ δ : upv ` u′qacv ′

für (b, p, c , q,N) ∈ δ : upv ` uqcv ′

188

Akzeptanz durch LBA

LBA M = (X ,Q, Γ, δ, q0,F ,2)

M akzeptiert das Wort w ∈ X ∗ gdw.eine Folge k0, . . . , kn von Konfigurationen ki ∈ Γ∗ × Q × Γ∗

exisiert, so dass gilt:1. k0 = q0w ist die Startkonfiguration mit Eingabe w

2. k0 ∈ Γ∗ × F × Γ∗ ist eine akzeptierende Konfiguration3. für jedes i ∈ {1, . . . , n} ist ki−1 ` ki ein zulässiger

Konfigurationsübergang

M akzeptiert die Sprache L(M) = {w ∈ X ∗ | M akzeptiert w}

L ⊆ X ∗ heißt LBA-akzeptierbar gdw. ein LBA M mit L = L(M)existiert.

189

LBA – BeispielLBA M = ({a, b, c}, {q0, q1, q2, q3, f }, {a, b, x ,2}, δ, q0, {f },2) mit

δ = { (2, q0,2, f ,N)

(2, q3,2, q0,R)

(a, q0, x , q1,R)

(a, q1, a, q1,R)

(a, q3, a, q3, L)

(b, q1, x , q2,R)

(b, q2, b, q2,R)

(b, q3, b, q3, L)

(c , q2, x , q3, L)

(x , q0, x , q0,R)

(x , q1, x , q1,R)

(x , q2, x , q2,R)

(x , q3, x , q3, L)}

akzeptiert L(M) = {anbncn | n ∈ N}190

Eigenschaften der Menge aller kontextsensitiven SprachenAbschlusseigenschaften:Sind L1 und L2 kontextsensitive Sprachen, dann sind auch

I L1 ∪ L2

I L1 ∩ L2

I L1

I L1 ◦ L2

I L∗1kontextsensitive Sprachen.Für kontextsensitive Sprachen ist das Wortproblem (Gilt w ∈ L?)algorithmisch entscheidbar.Die Menge aller durch (nichtdeterministische) LBA akzeptierbarenSprachen ist genau die Menge aller kontextsensitiven Sprachen.(hier ohne Beweis)Ob deterministische und nichtderteministische LBA die selbeSprachklasse akzeptieren, ist bisher unbekannt.

191

Was bisher geschah – Chomsky-Typ 3

Reguläre Sprachen (REG):erzeugt durch reguläre Grammatik (Chomsky-Typ 3),

akzeptiert von NFA, DFA, ε-NFA, . . .abgeschlossen unter ∪,∩, , ◦, ∗, R

algorithmisch entscheidbar : Wortproblem (in O(|w |)), Leerheit, =,⊆, Endlichkeit

Anwendungen z.B. Suchen von Zeichenketten in Texten,Darstellung von Bezeichnern, KonstantenRechtschreibprüfung

nicht-reguläre Sprachen , z.B. {anbn | n ∈ N}, Dyck-Sprachen,{w ∈ {a, b}∗ | w = wR}, {an2 | n ∈ N}Nachweis Nicht-Regularität durch Schubfachschluss

Nichtdeterministische und deterministische endliche Automatendefinieren dieselbe Sprachklasse.

192

Was bisher geschah – Chomsky-Typ 2Kontextfreie Sprachen (CF):

erzeugt durch kontextfreie Grammatik (Chomsky-Typ 2)akzeptiert von nichtdeterministischem Kellerautomaten (PDA)

abgeschlossen unter ∪, ◦, ∗, R

aber nicht unter ∩ undalgorithmisch entscheidbar : Wortproblem (in O(|w |3)), Leerheit,

EndlichkeitAnwendungen z.B. Parser, Beschreibung und Erkennung der

Syntax von natürlichen Sprachen, regulären undarithmetischen Ausdrücken und Programmiersprachen

nicht-kontextfreie Sprachen , z.B. {anbncn | n ∈ N},{ww | w ∈ {a, b}∗}, {an2 | n ∈ N}Nachweis Nicht-Kontextfreiheit durchPumping-Lemma für kontextfreie Sprachen

Deterministische Kellerautomaten definieren eine echte Teilmengeder von nichtdeterministischen Kellerautomaten definiertenSprachklasse.

193

Was bisher geschah – Chomsky-Typ 1

Kontextsensitive Sprachen:erzeugt durch kontextsensitive Grammatik (Chomsky-Typ 1)

akzeptiert von nichtdeterministischen LBA (hier ohne Beweis)abgeschlossen unter ∪,∩, , ◦, ∗, R

algorithmisch entscheidbar : Wortproblem (in O(2|w |))nicht-kontextsensitive Sprachen ? (später)

Ob deterministische und nichtderteministische LBA die selbeSprachklasse akzeptieren, ist bisher unbekannt (LBA-Problem).

194

Wiederholung LBA

Parameter des Maschinenmodelles LBA:I externer Speicher: Eingabeband aus Zellen (Länge = Länge

des Eingabewortes)I interner Speicher:

1. Zustand (Zugriff: Lesen und Schreiben) und2. Arbeitsband (mit Länge = Länge des Eingabewortes)

(Zugriff: Lesen und Schreiben, Bewegung auf Nachbarzelle)

I häufige (äquivalente) Darstellung:Arbeitsband = Eingabeband

195

Turing-Maschinen

(Verallgemeinerung von LBA mit beliebig langem Arbeitsband)

Parameter des Maschinenmodelles TM:I externer Speicher: Eingabeband aus ZellenI interner Speicher:

1. Zustand (Zugriff: Lesen und Schreiben) und2. beidseitig unendliches Arbeitsband

(Zugriff: Lesen und Schreiben, Bewegung auf Nachbarzelle)

I häufige (äquivalente) Darstellung:beidseitig unendliches Eingabeband = Arbeitsband

196

Turing-Maschine – Definition

Turing-Maschine (TM) M = (X ,Q, Γ, δ, q0,F ,2) mitX endliches EingabealphabetQ endliche Menge von ZuständenΓ ⊃ X endliches Arbeitsalphabetδ ⊆ (Γ× Q × Γ× Q × {L,R,N})Übergangsrelation

q0 StartzustandF akzeptierende Zustände2 ∈ Γ \ X Leere-Zelle-Symbol

TM M heißt deterministisch gdw.für jedes a ∈ Γ und jedes q ∈ Q gilt

| {(a, q, b, p, x) | p ∈ Q, b ∈ Γ, x ∈ {L,R,N}} ∩ δ| ≤ 1

197

Beispiele für Turing-MaschinenI TM M1 = ({a, b}, {q0, f }, {a, b,2}, δ, q0, {f },2) mit

δ = {(a, q0, a, q0, L), (b, q0, b, q0, L), (2, q0,2, f ,R)}

I TM M2 = ({a, b}, {q0, qa, qb, f }, {a, b,2}, δ, q0, {f },2) mit

δ =

(a, q0,2, qa,R), (b, q0,2, qb,R),(a, qa, a, qa,R), (b, qa, b, qa,R),(a, qb, a, qb,R), (b, qb, b, qb,R),(2, q0,2, f ,R), (2, qa, a, f ,R), (2, qb, b, f ,R)

I TM M3 = ({1}, {q0, q1, q2, q3, q4, f }, {1, x ,2}, δ, q0, {f },2) mit

δ = {(1, q0, 1, q1,R), (1, q1, x , q2,R), (1, q2, 1, q3,R)}∪ {(1, q3, x , q2,R), (1, q4, 1, q4, L), (x , q1, x , q1,R)}∪ {(x , q2, x , q2,R), (x , q3, x , q3,R), (x , q4, x , q4, L)}∪ {(2, q1,2, f , L), (2, q2,2, q4, L), (2, q4,2, q0,R)}

198

Konfigurationen einer TM

TM M = (X ,Q, Γ, δ, q0,F ,2)

Konfiguration uqv ∈ (Γ∗ × q × Γ∗) bedeutet:I aktueller Bandinhalt: w = uvI aktueller Zustand der TM: qI Schreib-/Lesekopf der TM zeigt auf erstes Symbol von v

(Leere-Zelle-Symbol, falls v = ε)

Startkonfigurationen q0w mit w ∈ X ∗

akzeptierende Konfigurationen uqv mit q ∈ FKonfigurationsübergänge von upv mit u = u′a und v = bv ′:

für (b, p, c , q,R) ∈ δ : upv ` ucqv ′

für (b, p, c , q, L) ∈ δ : upv ` u′qacv ′

für (b, p, c , q,N) ∈ δ : upv ` uqcv ′

199

Akzeptanz durch TM

TM M = (X ,Q, Γ, δ, q0,F ,2)

M akzeptiert das Wort w ∈ X ∗ gdw.eine Folge k0, . . . , kn von Konfigurationen ki ∈ Γ∗ × Q × Γ∗

exisiert, so dass gilt:1. k0 = q0w ist die Startkonfiguration mit Eingabe w

2. k0 ∈ Γ∗ × F × Γ∗ ist eine akzeptierende Konfiguration3. für jedes i ∈ {1, . . . , n} ist ki−1 ` ki ein zulässiger

Konfigurationsübergang

M akzeptiert die Sprache L(M) = {w ∈ X ∗ | M akzeptiert w}

L ⊆ X ∗ heißt Turing-akzeptierbar gdw. eine TM M mit L = L(M)existiert.

200

Ende der Berechnung einer Turing-Maschine

Möglichkeiten für Berechnungen der TM M für ein Eingabewort w :1. Berechnung endet in einer akzeptierenden Konfiguration upv

(d.h. p ∈ F ),2. Berechnung endet in einer nicht-akzeptierenden Konfiguration

upv (d.h. p 6∈ F ),3. Berechnung endet nicht (unendliche Berechnung).

Im Fall 1 akzeptiert M das Eingabewort w , in Fall 2 und 3 nicht.

Zu jeder TM M existiert eine TM M ′, so dass L(M) = L(M ′) undin M ′ jede endliche nicht-fortsetzbare Berechnung in einerakzeptierenden Konfiguration endet.(d.h. Fall 2 kommt in M ′ nicht vor)

201

Alternative Akzeptanzbedingung für TMTM M = (X ,Q, Γ, δ, q0,F ,2) hält in einer Konfigurationuqv ∈ Γ∗ × Q × Γ∗ gdw. aus uqv kein Konfigurationsübergang in Mmöglich ist.

Zu jeder TM M existiert eine TM M ′ mit L(M) = L(M ′) ohneNachfolgekonfigurationen aus akzeptierenden Konfigurationen.(evtl. neuen akzeptierenden Zustand hinzufügen)

FaktZu jeder TM M existiert eine TM M ′ mit L(M) = L(M ′), die nur inakzeptierenden Konfigurationen hält.(Schleifen in nicht-akzeptierenden Zuständen hinzufügen)

FaktZu jeder TM M existiert eine TM M ′, so dass für jedes w ∈ Γ∗:M akzeptiert w gdw. M ′ bei Eingabe von w hält.

akzeptierende Zustände bei Akzeptanz durch Halt irrelevant(analog PDA-Akzeptanz durch leeren Keller)

202

Nichtdeterministische TM

TM M = ({0, 1}, {q0, q1, f }, {0, 1,2}, δ, q0, {f },2) mit

δ = { (0, q0, 1, q0,R)

(1, q0, 1, q0,R)

(1, q0, 1, q1,R)

(1, q1, 1, q1,R)

(2, q1,2, f ,N)}

akzeptiert z.B. das Wort 11011 mit (u.A.) folgender Berechnung

q011011 ` 1q01011 ` 11q0011 ` 111q011 ` 1111q11` 11111q12 ` 11111f 2

203

Simulation nichtdeterministischer TM

SatzZu jeder nichtdeterministischen TM M existiert einedeterministische TM M ′ mit L(M) = L(M ′).

Beweisidee:Menge aller möglichen Berechnungen von M bei Eingabe von wbilden einen Baum (evtl. mit unendlichen Pfaden)

Knoten: KonfigurationenWurzel: Startkonfiguration (Startzustand, Eingabewort)Blätter: akzeptierende KonfigurationKanten: zulässige Konfigurationsübergänge in M

M ′ führt Breitensuche in diesem Baum durch(simuliert parallele Berechnung aller Möglichkeiten, dovetailing),Bandinhalt von M ′ sind Konfigurationen aus MM ′ akzeptiert, sobald eine akzeptierende Konfiguration von M aufdem Arbeitsband steht.

204

Was bisher geschah

Turing-Maschine (X ,Q, Γ, δ, q0,F ,2)

I akzeptiert Sprache L ⊆ X ∗

(durch akzeptierende Zustände oder Halt)I ändert i.A. während der Berechnung den Inhalt (w ∈ Γ∗) des

Arbeitsbandes (Nebenwirkung)

deterministische und nichtdeterministische TM akzeptieren dieselbeSprachklasse(Breitensuche im Berechnungsbaum, dovetailing)

205

Beispiel

TM M = ({0, 1, •}, {q0, q1, q2, q3, q4, q5, f }, {0, 1, •,2}, δ, q0, {f },2)mit

δ = { (0, q0, 0, q0,R), (0, q1, •, q2, L)

(1, q0, 1, q0,R), (1, q1, •, q3, L)

(•, q0, •, q1,R), (2, q1,2, q4, L)

(•, q2, 0, q5,R), (•, q3, 1, q5,R)

(•, q4,2, f , L), (•, q5, •, q1,R)}

L(M) = L((0 + 1)∗ • (0 + 1)∗)

Auf dem Band verschiebt M während der Berechnungden Teil nach dem • um eine Zelle nach links (Nebenwirkung).

206

Operationen auf TM-akzeptierbaren Sprachengegeben: TM A, TM B (Akzeptanz durch Halt)gesucht: TM C mit

∩: L(C ) = L(A) ∩ L(B)(sequentieller Akzeptanztest durch beide TM)

∪: L(C ) = L(A) ∪ L(B)(verschränkter Akzeptanztest durch beide TM)

◦: L(C ) = L(A) ◦ L(B)(nichtdeterministische Zerlegung und verschränkter Test)

∗: L(C ) = L(A)∗

(nichtdeterministische Zerlegung und verschränkter Test)R : L(C ) = L(A)R

(Vorbereitung: auf dem Arbeitsband w durch wR ersetzen)

mit Turing-Maschinen für „Unterprogramme“,z.B. Verschieben, Kopieren, Zerlegen von Wörtern,Steuerung der sequentiellen und verschränkten (pseudo-parallelen)Ausführung mehrerer TM

207

Beispiel: Sprache vom Chomsky-Typ 0Regeln l → r mit l ∈ (T ∪ N)+, r ∈ (T ∪ N)∗

G = ({S ,T , }, {0, 1},P, S) mit

P =

S → 1S101S → 01S00S → 110S110S0 → T0T0 → T1S1 → T1T1 → TT → ε

Gilt ε ∈ L(G ) ?

S → 110S11→ 11001S0011→ 11001110S110011→ 110011101S101110011→ 11001110T01110011→∗ 110T011→ 11T11→ 1T1→ T → ε

208

TM und Sprachen vom Chomsky-Typ 0SatzDie Menge aller Sprachen, die von einer TM akzeptiert werden, ist genaudie Menge aller Sprachen vom Chomsky-Typ 0.Idee der Konstruktionen:

I Grammatik → TM:M berechnet für das Eingabewort w (letztes Wort einer Ableitung)eine Ableitung in der Grammatik „rückwärts“.(Bei jeder Regelanwendung wird der aktuelle Bandinhalt geeignetverschoben.)TM akzeptiert, wenn Bandinhalt = Startsymbol

I TM → Grammatik:Grammatik erzeugt „Kandidaten“ w ′ für jedes Eingabewort w .Grammatik-Regeln beschreiben die lokalen Änderungen beiKonfigurationsübergängen der TM.(Simulation der Berechnung der TM auf w durch Ableitung in derGrammatik)Wird in der Ableitung ein akzeptierender Zustand errreicht,Übersetzung des Kandidaten w ′ in Terminalwort w .

209

Beispiel: Sprache vom Chomsky-Typ 1monotone GrammatikRegeln l → r mit l , r ∈ (T ∪ N)+ mit |l | ≤ |r |G = ({S ,R,T ,A,B}, {a, b},P, S) mit

P =

S → RTR → RBBT → AABA → AARA → baaA → aa

Ableitung für das Wort baaaa

S → RT → RBT → RBBT → RBBBT

→ RBBAA→ RBAAA→ RAAAA

→ baAAA→ baaAA→ baaaA→ baaaa

nichtverkürzende Grammatik, also sind Wörter in Zwischenschrittennie länger als das abgeleitete Wort

SatzDie Menge aller Sprachen, die von einer TM mit linearbeschränktem Band akzeptiert werden, ist genau die Menge allerSprachen vom Chomsky-Typ 1.

210

Zusammenfassung: Turing-akzeptierbare Sprachen

I Deterministische TM akzeptieren dieselbe Sprachklasse wienichtdeterministische TM,und zwar genau alle Sprachen vom Chomsky-Typ 0

I Die Menge aller TM-akzeptierbaren Sprachen ist abgeschlossenunter ∪,∩, ◦, ∗,aber nicht unter (Gegenbeispiel später)

I Wortproblem, Leerheit, Endlichkeit und Gleichheit sind fürTM-akzeptierbare Sprachen nicht algorithmisch entscheidbar

alternative Bezeichnung:Die Menge aller TM-akzeptierbaren Sprachen ist genau die Menge allerTuring-aufzählbaren Sprachen.

211

Zusammenfassung: LBA-akzeptierbare Sprachen

I (Nichtdeterministische) linear beschränkte TM (LBA)akzeptieren genau alle Sprachen vom Chomsky-Typ 1(kontextsensitiv)

I Ob deterministische und nichtdeterministische LBA dieselbeSprachklasse akzeptieren, ist unbekannt (LBA-Problem)

I Die Menge aller von LBA akzeptierten Sprachen(Chomsky-Typ 1) ist abgeschlossen unter ∪,∩, , ◦, ∗, R

I Wortproblem ist für LBA-akzeptierbare Sprachen algorithmischentscheidbar.(schon früher gezeigt: Wortproblem für nichtverlängerndeWortersetzungssysteme)

I Leerheit, Endlichkeit und Gleichheit kontextsensitiver Sprachensind nicht algorithmisch entscheidbar.

212

Wiederholung: TM für Verschiebung

(jetzt nur für Wörter aus {1}∗)

TM M = ({1, •}, {q0, q1, q2, q3, q4, q5, f }, {1, •,2}, δ, q0, {f },2) mit

δ = { (1, q0, 1, q0,R)

(•, q0, 1, q1,R)

(1, q1, 1, q1,R)

(2, q1,2, q2, L)

(1, q2,2, f , L)}

akzeptiert jedes Eingabewort aus 1∗ • 1∗,verschiebt dabei den Teil nach dem • um eine Zelle nach links

als Berechnung mit Unärdarstellungen natürlicher Zahlen: Addition

213

TM zur Berechnung von Funktionen

Idee: deterministische TM M berechnet eine FunktionfM : X ∗ → Γ∗

Eingabe w ∈ X ∗: Inhalt des Arbeitsbandes bei Start derBerechnung (Eingabewort)

Ausgabe v ∈ Γ∗: Inhalt des Arbeitsbandes nach Halt der TM

Wenn M bei Eingabe von w nicht hält, ist der Wert fM(w) nichtdefiniert.

TM M berechnet i.A. eine partielle Funktion

fM : X ∗ → Γ∗

da fM nur für durch Halt akzeptierte Wörter w ∈ X ∗ definiert ist

214

Turing-berechenbare FunktionenJede deterministische TM M definiert die (partielle) FunktionfM : X ∗ → Γ∗, wobei ∀w ∈ X ∗

fM(w) =

{v falls Bandinhalt v , nachdem M hältnicht definiert falls M nicht hält

Beispiel: M = ({a, b}, {q0, q1, q2, q3}, {a, b,2}, δ, q0,2) mit

δ = {(a, q0,2, q1,R), (b, q0,2, q2,R), (2, q0,2, q0,N)}∪{(a, q1, a, q1,R), (b, q1, b, q1,R), (2, q1, a, q3,N)}∪{(a, q2, a, q2,R), (b, q2, b, q2,R), (2, q2, b, q3,N)}

definiert die Funktion

fM(w) =

{vx falls w = xv mit x ∈ {a, b} und v ∈ {a, b}∗

nicht definiert falls w = ε

Eine Funktion f : X ∗ → X ∗ heißt Turing-berechenbargdw. eine deterministische TM M mit f = fM existiert.

215

Turing-berechenbare Funktionen auf NCodierung natürlicher Zahlen, z.B. in

I Unärcodierung c1 : N→ {1}∗

I Binärcodierung c2 : N→ {0, 1}∗

Beispiele:I M = ({1}, {q0, q1}, {1,2}, δ, q0,2) mitδ = {(q0, 1, q0, 1,R), (q0,2, q1, 1,N)}berechnet die Funktion fM(x) = x + 1 in Unärcodierung

I M = ({0, 1}, {q0, q1, q2, q3, f }, {0, 1,2}, δ, q0,2) mit

δ = {(0, q0, 0, q0,R), (1, q0, 1, q0,R), (2, q0,2, q1, L)}∪{(0, q1, 1, q3, L), (1, q1, 0, q2, L), (2, q1,2, q1,N)}∪{(0, q2, 1, q3, L), (1, q2, 0, q2, L), (2, q2, 1, f ,R)}∪{(0, q3, 0, q3, L), (1, q3, 1, q3, L), (2, q3,2, f ,R)}

definiert die Funktion fM(x) = x + 1 in Binärcodierung (ohneführende 0)

216

Beispiel: Unärcodierung → Binärcodierung

f : {1}∗ → {0, 1}∗ Transformation Unär-Binärcodierungwird (z.B.) berechnet von

TM M = ({1}, {q0, q1, q2, q3, q4, f }, {1, 0, x , y ,2}, δ, q0, {f },2)mit

δ =

(q0, 1, q0, x ,R), (q0,2, q1,2, L),(q1, x , q1, x , L), (q1,2, q2,2,R),(q2, x , q3, y , L), (q2,2, q4,2, L),(q2, y , q2, y ,R), (q2, 1, q2, 1,R), (q2, 0, q2, 0,R),(q3,2, q2, 1,R), (q3, 0, q2, 1,R),(q3, 1, q3, 0, L), (q3, y , q3, y , L),(q4, y , q4,2, L), (q4, 0, f , 0,N), (q4, 1, f , 1,N)

217

Mehrstellige Turing-berechenbare Funktionen auf NCodierung von Tupeln (x1, . . . , xk) ∈ Nk durch

c(x1) • c(x2) • · · · • c(xk) mit Trennzeichen •

Beispiel: TM M = ({1, •}, {q0, q1, q2, f }, {1, •,2}, δ, q0,2) mit

δ = {(1, q0, 1, q0,R), (•, q0, 1, q1,R), (2, q0,2, q0,N)}∪{(1, q1, 1, q1,R), (•, q1, •, q1,N), (2, q1,2, q2, L)}∪{(1, q2,2, f ,N)}

definiert die Funktion fM(x , y) = x + y (Unärcodierung)

Eine Funktion f : Nk → N heißt Turing-berechenbar gdw. einedeterministische TM M existiert, so dass für jede Eingabe(x1, . . . , xk) ∈ Rk gilt

f (x1, . . . , xk) = y gdw. fM(c(x1) • · · · • c(xk)) = c(y)

218

Nicht Turing-berechenbare FunktionenIst jede partielle Funktion f : X ∗ → X ∗

(f : X ∗ → Y ∗, f : N→ N, f : Nn → N) Turing-berechenbar?

Nein (Gegenbeispiel später)

Begründung: (Aussage für X = {0, 1} zu zeigen, genügt)

1. Wieviele Turing-Maschinen über einem endlichen Alphabet gibt es?abzählbar viele(weil TM endlich codiert werden können,nach erstem Diagonalverfahren von Cantor)

2. Wieviele partielle Funktionen f : X ∗ → X ∗ gibt es?überabzählbar viele(zweites Diagonalverfahren von Cantor)

Damit existieren sogar sehr viel mehr (überabzählbar viele) partielleFunktionen f : X ∗ → X ∗ (f : X ∗ → Y ∗, f : N→ N, f : Nn → N),die nicht von TM berechnet werden können.

Warum sind TM als Berechnungsmodell trotzdem interessant?

219

Intuitiver Berechenbarkeitsbegriff

Eine partielle Funktion f : X ∗ → X ∗ ist berechenbar, fallsI eine Rechenvorschrift oderI ein Algorithmus oderI ein Programm (in beliebiger Programmiersprache) oderI eine deterministische Turingmaschine

existiert, welche für jedes x ∈ N bei Eingabe von x den Wert f (x)ausgibt, falls f (x) definiert ist.

weitere Berechnungsmodelle:Registermaschinen, while-Programme,partiell rekursive Funktionen, λ-Kalkül, . . .

(mehr dazu in LV später im Studium)

220

These von Church

(Alonzo Church 1903-1995)

Für alle bisher vorgeschlagenen intuitiven Definitionen derBerechenbarkeit lässt sich beweisen, dass sie dieselbe Klasse vonFunktionen repräsentieren.

These von Church:Die Menge aller Turing-berechenbaren Funktionen ist genau dieMenge aller intuitiv berechenbaren Funktionen.

(Diese Aussage ist sinnvoll, aber wegen des Bezugs auf denungenauen Begriff „Intuition“ nicht beweisbar.)

221

Was bisher geschah

Sprache L ⊆ X ∗ heißt Turing-akzeptierbargdw. eine TM M mit L(M) = L existiert

partielle Funktion f : X ∗ → X ∗ heißt Turing-berechnbargdw. eine deterministische TM M existiert, die fberechnet, d.h. bei Eingabe w

I falls f (w) nicht definiert ist, nicht hältI falls f (w) = v , mit Bandinhalt v hält,

Ausdrucksstärke von Berechnungsmodell TM undanderen Berechnungsmodellen (RAM, goto-Programme,while-Programme, λ-Kalkül,. . . )äquivalent (Nachweise in der Fachliteratur)

I intuitiver BerechenbarkeitsbegriffI These von Church

222

Universelle (programmiebare) TMDefinition von TM (X ,Q, Γ, δ, q0,F ,2) ist endliche Beschreibung für

I Maschinenmodell zur Akzeptanz von Sprachen L

Eingabe: w ∈ X ∗

Ausgabe: I Halt und Ja, falls w ∈ L oderI Halt und Nein, falls w 6∈ L oderI kein Halt

I (deterministische TM als) Berechnungsmodell zurBerechnung partieller Funktionen f : X ∗ → Γ∗

Eingabe: w ∈ X ∗

Ausgabe: I Halt und f (w) ∈ Γ∗ oderI kein Halt

nach These von Church (Ausdrucksstärke von TM) existierenuniverselle TM (programmierbare TM), die

I endliche Beschreibungen von TM interpretieren und damitI Berechnungen jeder TM simulieren (den durch die TM definierten

Algorithmus ausführen) kann

endliche Beschreibung einer TM ist Programm zur Berechnung einerFunktion / Ausführung eines Algorithmus (durch universelle TM) 223

Entscheidbarkeit von Sprachencharakteristische Funktion einer Menge (Sprache) L ⊆ X ∗:

χL : X ∗ → {0, 1},wobei ∀w ∈ X ∗ : χL(w) =

{1 falls w ∈ L

0 sonst

Sprache (Menge) L ∈ X ∗ heißt entscheidbar gdw.die Funktion χL berechenbar ist.

Jede entscheidende TM hält bei jeder Eingabe.

Sprache (Menge) L ∈ X ∗ heißt semi-entscheidbar gdw. die„halbe“ charakteristische Funktion χ′L : X ∗ → {0, 1} berechenbar ist:

∀w ∈ X ∗ : χ′L(w) =

{1 falls w ∈ L

nicht definiert sonst

FaktEine Sprache ist genau dann semi-entscheidbar, wenn sieTuring-akzeptierbar ist.

224

Beispiele entscheidbarer Sprachen

I jede endliche Sprache L = {w1, . . . ,wn}(für jedes i nacheinander Test, ob Eingabe = wi )

I {a(2n) | n ∈ N},I jede reguläre , kontextfreie, kontextsensitive Sprache,I Menge aller Primzahlen (z.B. in Unärdarstellung),I Menge aller Primzahlzwillinge, d.h.

Paare (p, p + 2) mit Primzahlen p und p + 2

225

Abschlusseigenschaften

SatzEine Sprache L ist genau dann entscheidbar, wenn L und LTM-akzeptierbar sind.Idee: „parallele“ Ausführung der MaschinenM mit L(M) = L und N mit L(N) = L auf Eingabe w ,M hält, falls w ∈ L, sonst hält NDie Menge aller entscheidbaren Sprachen ist abgeschlossen unter

Vereinigung wegenχL∪L′(w) = max(χL(w), χL′(w)) berechenbar

Schnitt wegenχL∩L′(w) = min(χL(w), χL′(w)) berechenbar

Komplement wegenχL(w) = 1− χL(w) berechenbar

Achtung (Unterschied zu TM-akzeptierbaren Sprachen):Aus der TM-Akzeptierbarkeit von L folgt i.A. nicht dieTM-Akzeptierbarkeit von L.

226

Spezielles Halteproblem für TM

c(M): endliche Codierung c(M) der TM M (z.B. als Binärwort)

Das spezielle Halteproblem ist die Sprache

S = {c(M) | M hält bei Eingabe c(M)}

SatzDie Sprache S ist Turing-akzeptierbar.

Frage: Ist die Sprache S entscheidbar?

227

Unentscheidbarkeit des speziellen Halteproblems

SatzEs existiert keine TM, welche das spezielle Halteproblem (die Sprache S)entscheidet, d.h. die folgende Funktion berechnet:

χS(w) =

1 falls w = c(M) für eine TM M undM hält bei Eingabe von w

0 sonst

indirekter Beweis: (analog Barbier-Problem)Annahme: N ist TM mit fN = χS

Konstruktion einer TM N ′, so dass für jede TM M gilt:

fN′(c(M)) =

{nicht definiert falls M bei Eingabe von c(M) hält1 falls M bei Eingabe von c(M) nicht hält

Ist fN′(c(N ′)) definiert?

Widerspruch, eine solche TM N kann also nicht existieren.

228

Komplement des speziellen HalteproblemsSpezielles HP:

S = {c(M) | M hält bei Eingabe c(M)}Komplement des speziellen HP:

S =

{w | w ist keine Codierung einer TM oder

w = c(M) und M hält bei Eingabe c(M) nicht

}

FolgerungDie Sprache S ist nicht Turing-akzeptierbar.Beweisidee (indirekt):

I bekannt:1. S ist TM-akzeptierbar.2. S ist nicht entscheidbar.3. S TM-akzeptierbar ∧ S TM-akzeptierbar → S entscheidbar

I Annahme: S ist TM-akzeptierbar.dann ist S entscheidbar wegen 1. und 3.Widerspruch zu 2., also Annahme falsch,also S nicht TM-akzeptierbar.

229

Folgerungen aus der Unentscheidbarkeit von SKeine der folgenden Probleme (Sprachen) ist entscheidbar:

A = {c(M) • w | M hält bei Eingabe w}allgemeines Halteproblem

E = {c(M) | M hält bei Eingabe ε}Halteproblem mit leerer Eingabe

T = {c(M) | M hält für jede beliebige Eingabe}Totalitätsproblem

I = {c(M) | M hält für irgendeine Eingabe}

N = {c(M) | M hält für keine Eingabe}

230

Praktische Bedeutung

nach These von Church:Das Halteproblem ist für kein intuitives Berechnungsmodellentscheidbar.

Es existiert kein Programm, welches für jedes beliebige ProgrammP feststellt, ob P immer (für jede Eingabe) hält.(Unentscheidbarkeit des Totalitätsproblems)

Es existiert kein Programm, welches für jedes beliebige Paar (P, v)feststellt, ob das Programm P bei Eingabe von v anhält.(Unentscheidbarkeit des allgemeinen Halteproblems)

Solche negativen Aussagen sind nützlich,z.B. um Arbeitskraft- und -zeitverschwendung zu vermeiden.

231

Spezialfälle

Für spezielle Programme P und Eingaben w lässt sich häufigautomatisch feststellen, ob P bei Eingabe von w anhält.

realistische Ziele:Anwendung: Programme verwenden, für die Termination für alle

(relevanten) Eingaben bewiesen wurde(z.B. als Gerätetreiber)

Forschung: möglichst viele und große Klassen von Programmenund Eingaben finden, für die sich Termination (oderNicht-Termination) beweisen lässt,(Weiter-)Entwicklung von Verfahren zum Nachweisder Termination von Programmen

232

Zusammenfassung Theoretische Informatik WS15/16

Prüfung (Klausur):Montag, 8.2.2016 um 12:30 - 14:00 Uhr in HS LNW 006Zur Prüfung ist zugelassen, wer alle folgenden Bedingungen erfüllt:

Autotool: ≥ b23/2c = 11 Punkte für Pflicht-Aufgaben undÜbungen: ≥ 3 Punkte für erfolgreiches Vorrechnen

28 Zulassungen: 15 INB1, 13 INB2

Aufgabentypen wie in Übungsserien

zugelassene Hilfsmittel:ein (beidseitig) handbeschriebenes A4-Blatt

233

Inhalt – Theoretische Informatik WS15/16

(nach Modulbeschreibung)

I Formale SprachenI WortersetzungssystemeI Grammatiken

Chomsky-Hierarchie (für Grammatiken und Sprachen)I Maschinenmodelle

I Endliche AutomatenI KellerautomatenI Turingmaschinen

I Ausblick Berechenbarkeit (von partiellen Funktionen)I Ausblick Entscheidbarkeit (von Sprachen / Mengen)

(mehr in Master-LV zur theoretischen Informatik)

234

Formale Sprachen

I endliches Alphabet XI Wort w ∈ X ∗

Operationen auf Wörtern: ◦,∗ ,RRelationen auf Wörtern: Infix, Präfix, Postfix, lexikographischeund quasilexikographische Ordnung

I (formale) Sprache L ⊆ X ∗

Operationen auf Sprachen: ∪,∩, , \, ◦,∗ ,R

I Reguläre Ausdrücke(endliche Darstellung unendlicher Sprachen)

Wortersetzungssystem (SRS) S ⊆ X ∗ × X ∗

(endliche Darstellung unendlicher Sprachen)Ableitungsrelation →S zum SRS S , transitiver Abschluss →∗SWortproblem für Wortersetzungssysteme:{(S , u, v) | S ⊆ X ∗ × X ∗ (endlich) ∧v ∈ X ∗ ∧ v ∈ X ∗ ∧ u →∗s v}(Menge aller Tripel (S , u, v) mit u →∗s v)

235

Grammatiken

(endliche Darstellung unendlicher Sprachen)Grammatik G = (N,T ,P,S)

Ableitungen in Grammatiken

Ableitungsbäume

eindeutige / mehrdeutige Grammatiken

von Grammatik G erzeugte Sprache L(G )

Wortproblem für Grammatiken:{(G , v) | G = (N,T ,P,S) ∧ v ∈ T ∗ ∧ v ∈ L(G )}(Menge aller Paare (G , v) mit v ∈ L(G ))

236

Chomsky-HierarchieEine Grammatik G = (N,T ,P,S) ist vom Chomsky-Typ

0 immer,1 , falls für jede Regel (l → r) ∈ P gilt: |l | ≤ |r |

(monoton, kontextsensitiv)2 , falls Typ 1 und für jede Regel (l → r) ∈ P gilt: l ∈ N

(kontextfrei)3 , falls Typ 2 und für jede Regel (l → r) ∈ P gilt:l ∈ N und r ∈ (T ∪ TN)(regulär)

Sprache L hat Chomsky-Typ i gdw. eine Grammatik G mitChomsky-Typ i mit L(G ) = L \ {ε} existiertpraktisch: Zulassung der ε-Sonderregel:Grammatik G = (N,T ,P,S) hat auch dann Chomsky-Typ i , wennsie

I nur Regeln der für Chomsky-Typ i erlaubten FormI und evtl. die Regel S → ε enthält

237

Endliche AutomatenNFA A = (X ,Q, δ, I ,F )

I akzeptierende Pfade ∈ (I × Q∗ × F ) ∪ (I ∩ F )

I akzeptierte WörterI akzeptierte Sprache L(A) ⊆ X ∗

I Äquivalenz, IsomorphieI Eigenschaften:

vollständig, deterministisch, mit ε-Übergängen, MinimalautomatI Abschluss unter ∪,∩, , ◦,∗ ,R

I Nachweis Nicht-Regularität durch Schubfachschluss

NFA akzeptieren genau alle regulären Sprachen (Typ 3)= genau alle durch reguläre Ausdrücke darstellbaren Sprachen

Wortproblem für Typ-3-Sprachen in O(n) lösbar (Minimalautomat)(n – Länge des Eingabewortes)

Anwendung z.B. in String-Matching-Algorithmen(siehe LV Algorithmen und Datenstrukturen)

238

KellerautomatenPDA A = (X ,Q, Γ, δ, q0,F ,⊥)

I Konfiguration, KonfigurationenfolgeI akzeptierte WörterI akzeptierte SpracheI ÄquivalenzI Akzeptanz durch akzeptierende Zustände / leeren Keller

PDA akzeptieren genau die kontextfreien Sprachen (Typ 2).(DPDA akzeptieren echte Teilmenge)kontextfreie Sprachen:

I Chomsky-NormalformI CYK-Algorithmus (dynamische Programmierung)

löst Wortproblem für Typ-2-Sprachen in O(n3)I Abschluss unter ∪, ◦,∗ ,R , Schnitt mit regulären Sprachen

aber nicht unter ∩,I Nachweis Nicht-Kontextfreiheit durch

Pumping-Lemma für kontextfreie Sprachen

Anwendung z.B. beim Parsen von Programmen und (arithmetischen,regulären, logischen, . . . ) Ausdrücken 239

Turing-MaschinenTM M = (X ,Q, Γ, δ, q0,F ,2)

I deterministisch / nichtdeterministisch

I Konfiguration, Konfigurationenfolge

I akzeptierte Wörter

I akzeptierte Sprache L(M) ⊆ X ∗

I Akzeptanz durch akzeptierende Zustände / Halt

I Abschluss Turing-akzeptierbarer Sprachen unter ∪,∩, ◦,∗ ,Raber nicht unter

TM akzeptieren genau alle durch eine Grammatik erzeugten Sprachen(Chomsky-Typ 0).LBA (TM mit linear beschränktem Band) akzeptieren genau allekontextsensitiven Sprachen (Chomsky-Typ 1).

LBA-Problem (ungelöst): Ist jede von einen nichtdeterministischen LBAakzeptierte Sprache durch einen deterministischen LBA akzeptierbar?

240

Berechenbarkeit

von (partiellen) Funktionen

deterministische TM M = (X ,Q, Γ, δ, q0,F ,2) definiert (partielle)Funktion fM : Γ∗ → Γ∗ durch

fM(w) =

{v falls Bandinhalt v , nachdem M hältnicht definiert falls M nicht hält

Codierung ein- und mehrstelliger Funktionen auf N

These von Church:Die Menge aller intuitiv berechenbaren Funktionen ist genau dieMenge aller Turing-berechenbaren Funktionen.

241

Entscheidbarkeit

von Sprachen / Mengen

Spache L ⊆ X ∗ ist entscheidbar gdw. χL : X ∗ → {0, 1} mit

χL(w) =

{1 falls w ∈ L

0 sonst

berechenbar ist.

Menge aller entscheidbaren SprachenI genau die Menge aller Sprachen L, für die L und L

Turing-akzeptierbar sind,I abgeschlossen unter ∪,∩, , ◦,∗ ,R

Codierung von TM

universelle TM (programmierbar)

242

Probleme als Sprachen

Problem =Menge (Sprache) der Codierungen aller korrekten Instanzen

z.B. Wortproblem für Typ-3-GrammatikenWortproblem WPG3 = {(G ,w) | w ∈ L(G )}Parameter (Eingaben für Lösungsverfahren):

I Typ-3-Grammatik G = (N,T ,P, S) undI w ∈ T ∗

Frage: Gilt w ∈ L(G ) ?Antwort (mögliche Ausgaben des Lösungsverfahrens):

I ja, falls w ∈ L(G )I nein, falls w 6∈ L(G )

Instanzen z.B. mit G = ({S}, {a, b}, {S → aS |b},S):I (G , aab) ∈WPG3 (korrekte Instanz),I (G , aba) 6∈WPG3

243

Entscheidbarkeit – Beispiele

Beispiele entscheidbarer Sprachen:I Wortproblem für Typ-1,2,3-Grammatiken,

z.B. WPG3 = {(G ,w) | w ∈ L(G )}I NFA-Äquivalenzproblem: EqNFA = {(A,B) | L(A) = L(B)}

Beispiele unentscheidbarer Sprachen:I Wortproblem für Typ-0-GrammatikenI spezielles Halteproblem für TM:

H = {c(M) | TM M hält bei Eingabe von c(M)}I weitere HalteproblemeI Erfüllbarkeitsproblem der Prädikatenlogik:

SATFOL = {ϕ ∈ FOL(Σ,X) | Mod(ϕ) 6= ∅}I Wortproblem für Typ-0-Grammatiken:

WPG0 = {(G ,w) | w in G ableitbar}

244