Quelle - Automatentheorie Zusammenfassung

Aus Zweites Gehirn, dem persönlichen Wiki
Quelle - Automatentheorie Zusammenfassung
TypQuelle
Rohdateisources/Automatentheorie Zusammenfassung.pdf
AutorRené Gisler (Nutzer dieses Wikis)
InstitutionFFH Schweiz
Datum_quelle2002-02-20
FormatPDF, 50 Seiten, viele Diagramme (Automaten, Tabellen)
Erstellt2026-09-24
Aktualisiert2026-09-24
Tagstheoretische-informatik, automatentheorie, formale-sprachen, studium

Eigene Zusammenfassung zur theoretischen Informatik an der FFH Schweiz (Februar 2002). Sie reicht von endlichen Automaten über formale Grammatiken und die Chomsky-Hierarchie bis zu Berechenbarkeit und Komplexität.

Aufbau der Quelle

Seiten Thema Eingeflossen in
2–3 Wörter, Sprachen, Kleene-Stern Formale Sprache
2–12, 19 DFA, NFA, ε-Automaten, GFA, Minimierung, Pattern-Matching, Mealy/Moore Endlicher Automat
13–18 Reguläre Ausdrücke, Typ-3-Grammatiken, Abschluss, Pumping-Lemma Reguläre Sprache
20–31 Kontextfreie Grammatiken, CNF/GNF, Ableitungsbäume, EBNF, Kellerautomaten Kontextfreie Sprache
32–40 Kontextsensitive und Typ-0-Sprachen, Abzählbarkeit, LBA, Sprachklassen Chomsky-Hierarchie
35–39, 47 Turingautomaten, universelle Turingmaschine Turingmaschine
41–48 Turing-, LOOP-, WHILE-, GOTO-Berechenbarkeit, Church, Ackermann, Entscheidbarkeit Berechenbarkeit
49–50 O-Notation, P vs. NP, NP-Vollständigkeit Komplexitätstheorie

Kernaussagen

  1. Automaten (erkennend) und Grammatiken (erzeugend) beschreiben dieselben Sprachklassen. Sie ordnen sich in der Chomsky-Hierarchie: Typ 3 ⊂ Typ 2 ⊂ Typ 1 ⊂ Typ 0.
  2. Bei endlichen Automaten und Turingmaschinen ändert Nichtdeterminismus die Mächtigkeit nicht. Bei Kellerautomaten schon. Bei linear beschränkten Automaten ist es offen (LBA-Problem).
  3. Pumping-Lemmata zeigen, dass Sprachen nicht regulär oder nicht kontextfrei sind (Reguläre Sprache, Kontextfreie Sprache).
  4. Turing-, WHILE- und GOTO-Berechenbarkeit sind gleichwertig (Churchsche These). goto ist deshalb verzichtbar, LOOP ist schwächer (Berechenbarkeit).
  5. Entscheidbar heisst nicht praktikabel. P vs. NP ist offen (Komplexitätstheorie).

Bewertung

Einordnung (Claude)

Die Quelle ist eine Lernzusammenfassung. Die einleitenden Absätze der Kapitel stammen erkennbar wörtlich aus einem Lehrbuch oder Kursskript (Stil, Querverweise wie „Beispiel von Seite 29“, „haben wir … definiert“). Literaturangaben fehlen. Viele Beispiele, die Minimierung, das Komplement und die Übersichtstabellen auf S. 39–40 und 50 liegen nur als Grafik vor (teils handgezeichnet, teils aus einem Lehrbuch eingescannt). Beim ersten Ingest fehlte ein PDF-Renderer. Am 2026-09-24 wurden diese Seiten mit PyMuPDF gerendert und nachträglich ausgewertet. Die Beispiele und Tabellen sind jetzt in Endlicher Automat, Kontextfreie Sprache, Chomsky-Hierarchie, Turingmaschine, Berechenbarkeit und Komplexitätstheorie eingearbeitet. Wo ergänzt wurde, ist das als Claude-Einordnung markiert.

Fehler und Ungenauigkeiten in der Quelle
  • S. 25: Das Pumping-Lemma für kontextfreie Sprachen wird mit „Wörter regulärer Sprachen“ und „Anzahl der Zustände von A“ formuliert, offenbar vom regulären Fall kopiert. Richtig: eine von der Grammatik abhängige Konstante n (siehe Kontextfreie Sprache).
  • S. 32: „Mit kfS oder mit TYP-1 bezeichnen wir die Klasse der kontextsensitiven Sprachen“. Gemeint ist ksS.
  • S. 34/39: „Kontextsensitive Sprachen können das leere Wort nicht enthalten“. Das gilt nur bei streng monotonen Grammatiken. Üblich ist die Sonderregel S → ε, wenn S rechts nirgends vorkommt (siehe Chomsky-Hierarchie).
  • S. 28: Die Beschriftungen der Syntaxdiagramme für Option und Wiederholung sind vertauscht (siehe Kontextfreie Sprache).
  • S. 40: Die Tabellen-Überschriften (Abschlusseigenschaften, Entscheidbarkeit, Wortproblem) sind um eine Tabelle verschoben. Das „?“ zur Äquivalenz von DPDA war schon 2002 überholt (entscheidbar seit Sénizergues 1997) (siehe Chomsky-Hierarchie).
  • Tippfehler, die den Sinn nicht verändern: „Melay“, „Chromsky“, „Tuning-Berechenbarkeit“ (Texterkennungsfehler für „Turing“).

Neu angelegte Seiten

Verwandt

Links auf diese Seite

Kategorien: theoretische-informatik | automatentheorie | formale-sprachen | studium