"Automatentheorie 001.ps.gz" - читать интересную книгу автора

Automatentheorie

WS 1994/95 RWTH Aachen

Mitschrift

ii

Vorwort Die vorliegende Mitschrift der Vorlesung "Automatentheorie", gelesen von Prof. Dr. F. Baader im Wintersemester 1994/95 an der RWTH Aachen, ist genau das, was der Name sagt: Die geTEXte Form der Vorlesungsmitschrift einer unwissenden Studentin, angereichert mit einigen wenigen, nicht weiter gekennzeichneten privaten Erg"anzungen (in der Regel triviale Beweise, auf die Prof. Baader in der Vorlesung verzichtet hat). Es ist wahrscheinlich, dass sich an der einen oder anderen Stelle Fehler eingeschlichen haben. (Verbesserungsvorschl"age und "Fehlermeldungen" aller Art sind mir nat"urlich willkommen.) Deshalb ist dieses Schriftst"uck mit Vorsicht zu geniessen und von mir nur als kleine Unterst"utzung f"ur Leute gedacht, die sich mit der Vorlesung auseinandersetzen (wollen). Auf gar keinen Fall sollte es als "Skript" missverstanden werden. Dies ist es nicht!

Aachen, M"arz 1996 Claudia Krobb

e-mail: [email protected]

iii

iv Inhaltsverzeichnis

Inhaltsverzeichnis

Motivation und Einordnung 1 1 Regul"are Sprachen, endliche Monoide und logische Formeln 5

1.1 Regul"are Sprachen und endliche Automaten . . . . . . . . . . . . . . 5 1.2 Regul"are Sprachen und endliche Monoide . . . . . . . . . . . . . . . 8 1.3 Regul"are Sprachen und logische Formeln . . . . . . . . . . . . . . . . 19

2 Verallgemeinert-definite Sprachen und quantorenfreie Formeln 23

2.1 Verallgemeinert-definite Sprachen . . . . . . . . . . . . . . . . . . . . 23 2.2 Die zugeh"orige S-Variet"at . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Quantorenfreie Formeln . . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Sternfreie Sprachen 31

3.1 Die Sprachkasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Aperiodische Monoide . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 Formeln der Logik erster Stufe . . . . . . . . . . . . . . . . . . . . . 34

3.3.1 Beweis von "1 ) 2" von Satz 3.9 . . . . . . . . . . . . . . . . 35 3.3.2 Beweis von " 2 ) 1" von Satz 3.9 . . . . . . . . . . . . . . . . 35 3.3.3 Beweis der S"atze 3.12 und 3.16 . . . . . . . . . . . . . . . . . 39 3.4 Die Theorie der totalen Ordnung . . . . . . . . . . . . . . . . . . . . 45

4 Unendliche W"orter und B"uchi-Automaten 47 5 Unendliche W"orter und logische Formeln 65 6 Automaten auf endlichen B"aumen 85 7 Automaten auf unendlichen B"aumen 99 8 Baumautomaten und logische Formeln 111

v