Theoretische Informatik
Aus Informatik
Endliche Automaten
- Darstellung von Automaten
- Transduktor / Mealy-Automat
- Übungsaufgaben Transduktor
- Akzeptor
- Akzeptor zur Syntaxanalyse, Syntaxdiagramme
- Übungsaufgaben Akzeptor
- Epsilon-NEA
Von endlichen Automaten zu regulären Sprachen
- Reguläre Ausdrücke und reguläre Sprachen - Begriffsklärung
- Reguläre Ausdrücke
- Äquivalenz Endlicher Automaten und regulärer Sprachen
- Nichtreguläre Sprachen
- Übungsaufgaben
Formale Sprachen und Grammatiken
- Einführung - Beispiele
- Grammatiken und Formale Sprachen
- Allgemeine Regelsprachen
- Linkslineare Sprachen - reguläre Sprachen
- Äquivalenz links- bzw. rechtslinearer Sprachen und endlicher Automaten
- Übungsaufgaben reguläre Sprachen
- Erweiterte Backus - Naur - Form (EBNF)
- Kontextfreie Sprachen
- Übungsaufgaben
- Kontextsensitive Sprachen
Formale Sprachen und Automatenmodelle
- Zusammenhang zwischen Automaten und Sprachen
- Kellerautomaten
- Algorithmische Umsetzung von Kellerautomaten
- Übungsaufgaben
- Turingmaschine
- Übungsaufgaben
- Vergleich der Turingmaschine mit einem Computer