Automaten und Sprachen (WS 2024/2025) PDF

Automaten und Sprachen WS 2024/2025 Universität Leipzig Jakob Piribauer Skript zur Vorlesung Skript erstellt von Christel Baier, Manuela Berg, Walter Nauber Lehrstuhl für Algebraische und Logische Grundlagen der Informatik...

Automaten und Sprachen WS 2024/2025 Universität Leipzig Jakob Piribauer Skript zur Vorlesung Skript erstellt von Christel Baier, Manuela Berg, Walter Nauber Lehrstuhl für Algebraische und Logische Grundlagen der Informatik Fakultät für Informatik TU Dresden 1 Inhaltsverzeichnis Formale Sprachen und Automatentheorie 2 1 Grammatiken 7 2 Reguläre Sprachen 17 2.1 Endliche Automaten............................... 17 2.1.1 Deterministische endliche Automaten.................. 17 Literatur Die Vorlesung behandelt Automatentheorie und formale Sprachen. Die behandelten Konzep- te formaler Sprachen und der Automatentheorie bilden eine wichtige Grundlage z.B. für den Übersetzerbau, den Schaltkreisentwurf oder die Textverarbeitung. Die Inhalte der Vorlesung können zu großen Teilen in zahlreichen Lehrbüchern, die eine Ein- führung in die Theoretische Informatik anhand der Themenkomplexe formale Sprachen und Automatentheorie zum Ziel haben, nachgelesen werden. Eine Auswahl an Lehrbüchern, die den Inhalten der Vorlesung am nächsten kommen, ist: 1. A. Asteroth, C. Baier, Theoretische Informatik. Eine Einführung in Berechenbarkeit, Kom- plexität und formale Sprachen mit 101 Beispielen. Pearson Studium, 2002. 2. J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 4. Auflage, 2014 (dt. Version erhältlich). 3. D. Kozen, Automata and Computability. Springer, 2007. 4. H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation. Prentice Hall, 1998. 5. U. Schöning, Theoretische Informatik kurz gefaßt. Spektrum Akademischer Verlag, 4. Auflage, 2000. 6. T. Sudkamp, Languages and Machines. An Introduction to the Theory of Computer Science. Addison Wesley, 3. Auflage, 2006. 7. I. Wegener, Theoretische Informatik. B.G. Teubner, 1993. 1 Formale Sprachen und Automatentheorie Formale Sprachen und Automatenmodelle Formale Sprachen und Automatenmodelle wie endliche Automaten oder Kellerautomaten ha- ben zahlreiche Anwendungen in der Informatik. Zu den wichtigsten zählt der Compilerbau. Das Grobschema der ersten Phasen des Übersetzungsvorgangs ist in Abbildung 1 skizziert. Quellprogramm ↓ Scanner: lexikalische Analyse liefert eine Folge von Grundsymbolen ↓ Parser: syntaktische Analyse liefert einen Strukturbaum ↓ semantische Analyse maschinenunabhängige Optimierung Codeerzeugung und -optimierung ↓ Programm in Maschinensprache Abbildung 1: Grobschema des Übersetzungsvorgangs Das Ziel der lexikalischen Analyse ist die Erkennung und Codierung der Grundsymbole sowie die Ausblendung bedeutungsloser Zeichen und Zeichenketten (z.B. Kommentare und Leerzei- chen). Man unterscheidet vier Arten von Grundsymbolen: Schlüsselwörter: z.B. IF, THEN, BEGIN , etc., Spezialsymbole: z.B.