"Automatentheorie und formale Sprachen 004.ps.gz" - читать интересную книгу автораUniversit"at Trier Fachbereich IV - Informatik Christoph Meinel: Automatentheorie und Formale Sprachen Vorlesungsskript SS 2000 INHALTSVERZEICHNIS 1 Inhaltsverzeichnis 0 Vorbemerkungen 2 0.1 W"orter, Alphabete, Sprachen : : : : : : : : : : : : : : : : : : : : : : : : : 2 0.2 Graphen und B"aume : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 0.3 Relationen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 0.4 Mengen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 0.5 Komplexit"atsfunktionen : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7 1 Grammatiken 8 1.1 Beispiele : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 1.2 Definitionen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9 1.3 Chomsky - Hierarchie : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 1.4 Wortprobleme : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14 1.5 Syntaxb"aume : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 1.6 Backus-Naur-Form : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 19 2 Regul"are Sprachen 21 2.1 Deterministische und Nichtdeterministische endliche Automaten : : : : : : 21 2.2 Regul"are Ausdr"ucke : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 26 2.3 "Aquivalenzrelationen und Minimalautomaten : : : : : : : : : : : : : : : : : 29 2.4 Periodizit"atseigenschaften : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 2.5 Abschlusseigenschaften : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 34 2.6 Algorithmische Eigenschaften : : : : : : : : : : : : : : : : : : : : : : : : : 35 3.1 Normalformen : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 38 3.2 Pumping Lemma : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 40 3.3 Abschlusseigenschaften : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 43 3.4 Algorithmische Eigenschaften : : : : : : : : : : : : : : : : : : : : : : : : : 44 3.5 Pushdown Automaten : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 46 3.6 Deterministisch kontextfreie Sprachen : : : : : : : : : : : : : : : : : : : : : 52 4 Kontextsensitive und Typ 0-Sprachen 55 0 VORBEMERKUNGEN 2 0 Vorbemerkungen 0.1 W"orter, Alphabete, Sprachen ffl IN = f0; 1; 2; : : :g: nat"urliche Zahlen ffl \Sigma : endliche Menge (Alphabet) von Symbolen (Buchstaben) ffl w: endliche Folge von Buchstaben (Wort) ffl jwj: Zahl der Buchstaben von w (L"ange des Wortes) ffl 2: Wort, das aus der Buchstabenfolge der L"ange 0 besteht (sog. leeres Wort) ) j2j = 0 ffl Pr"afix: beliebiges Anfangsst"uck eines Wortes ffl Suffix: beliebiges Endst"uck eines Wortes ffl Konkatenation: Bildung eines Wortes durch Hintereinanderschreiben zweier W"orter ffl L (formale) Sprache: Menge von W"ortern "uber einem Alphabet ffl F"ur endliches Alphabet \Sigma : \Sigma 0 := f2g \Sigma i+1 := fw j w = w0a mit w0 2 \Sigma i, a 2 \Sigma g (i ? 0) \Sigma \Lambda := Si*0 \Sigma i \Sigma + := Si?0 \Sigma i = \Sigma \Lambda \Gamma f2g ffl Wir bezeichnen Konkatenation durch ffi: (\Sigma \Lambda ; ffi) ist ein Monoid (Halbgruppe mit neutralem Element), d.h. es gilt: |
|
|