INFORMATIK, SCHULE & CO MEDARD IMPRESSUM theoretische Informatik
Informatik Programmieren Überblick Konzepte DrScheme Java JavaScript x-Talk-Sprachen   Unterricht If1-11 Techn. Informatik Theoretische Informatik ITG Math.-naturw.-AG MATH-NAT-Wahlfach Mathematik Materialien Logik	Arbeitspapiere Automaten und formale Sprachen: Formale Sprachen, Überblick Chomsky-Hierarchie der formalen Sprachen und Automaten pdf Modellierung eines endlichen Automaten mit Scheme Berechenbarkeit: Mengen, Mächtigkeit und Potenzmenge pdf externe Verweise („Links”) Überblick theor. Informatik Grenzen der Berechenbarkeit	Definitionen Eine formale Sprache L besteht aus „Wörtern” (Zeichenketten), die wiederum durch Hintereinanderschreiben (Konkatenation) von Zeichen eines (endlichen) Alphabets gebildet werden Dabei gilt: Die Konkatenation ist assoziativ (z.B. (001)10 = 0(0110) = 00110) Die Länge eines Wortes = Anzahl der Zeichen = |00110| = 5 Das leere Wort (Symbol unterschiedlich, häufig wie das griechische kleine Epsilon) hat die Länge 0. TURING-Maschine (TM) Was ist eine Turing-Maschine ? Definition der TM (deterministisch) Die Turing-Maschine (inkl. Simulator) TM auf Hochschul-Niveau (inkl. Video-Vortrag) Turing Machine Simulator Applet (Näheres dazu) Über Alan Turing