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

Formale Sprachen

Skript zur Vorlesung

(Vorl"aufige Fassung)

Prof. Dr. Klaus-J"orn Lange

Dr. Henning Fernau

Dr. Birgit Jenner Erstellung der Version SS'95: J"org Hoss Im SS'98 ge"andert durch: Henning Fernau

19. M"arz 1999

"Uber dies Skriptum: Zweck dieses mittlerweile "uber f"unf Jahre hinweg gehaltenen Skriptums soll sein, Studierenden das rein mechanische Abschreiben des Tafelinhalts abzunehmen und sie statt dessen in die Lage zu versetzen, den eigentlichen Erl"auterungen der Dozenten zu folgen. Ein Skriptum ist kein Lehrbuch und daher auch nur bedingt zum Selbststudium geeignet. Die angegebenen B"ucher zu unserem Thema leisten sicher hier einen besseren Dienst.

Im Sommersemester 1998 wurde die Veranstaltung ausnahmsweise nur dreist"undig gelesen, weshalb in jener Version des Skriptums das letzte Kapitel ("uber Komplexit"atstheorie) fehlt.

Hin und wieder sind in den Skripttext "Ubungsaufgaben eingestreut. Wir m"ochten Sie ermuntern, diese zu Ihrer eigenen Kontrolle zu bearbeiten. Wenn Sie eigene Ausarbeitungen von uns nachsehen lassen wollen, so sind wir gerne dazu bereit.

Nat"urlich stehen wir Ihnen auch bei Fragen zur Vorlesung oder den "Ubungen stets zur Verf"ugung.

1 1 Voraussetzungen und Grundlagen Alle folgenden Grundlagen sollten aus den Grundvorlesungen bekannt sein und sind nur zur Wiederholung und zur Festsetzung der Schreibweisen aufgef"uhrt. F"ur eine fundierte Einf"uhrung in den Bereich der formalen Sprachen wird auf [13] und [8] verwiesen.

Ein weiteres Ziel dieses Kapitels ist es, Querverbindungen zu anderen Vorlesungen aufzuzeigen. Vorweg noch: Wir verwenden das Zeichen () , um eine Genau-Dann-Wenn-Beziehung auszudr"ucken.

1.1 Diskrete Mathematik

ffl Unter dem kartesischen Produkt A \Theta B zweier Mengen A und B versteht man die Menge aller geordneten

Paare (a; b) mit a 2 A, b 2 B. A \Theta B := f (a; b) j a 2 A; b 2 B g

ffl Zwei Folgen (a1; a2; : : : ; an) und (b1; b2; : : : ; bm) sind genau dann gleich, wenn n = m und ai = bi f"ur alle

i = 1; : : : ; n.

ffl Eine (bin"are) Relation (zwischen A und B) ist eine Teilmenge des kartesischen Produkts zweier Mengen