Theoretische Informatik

Theoretische Informatik

1. Sprachen

   • Notation formaler Sprache
     • reguläre Ausdrücke
   • wird durch Grammatik beschrieben
     • Menge von Wörtern
   • wird aus Alphabet gebildet
   • kann endliche oder unendliche Wörter enthalten
   • kann durch Automaten akzeptiert werden

2. Automaten

   • Arten
     • deterministische
       • Übergangsfunktion eindeutig
     • nicht-deterministische
       • Übergangsfunktion nicht eindeutig
   • Funktionen
     • Überprüfung ob ein Wort zu der Grammatik/Sprache gehört
   • besteht aus
     • Übergangsfunktionen
     • Übergänge
     • Zustände
     • Start- und Endzustände

3. Grammatiken

   • besteht aus
     • Startsymbol
     • Regeln
     • Nichtterminlsymbol
     • Terminalsymbol
   • beschreibt, welche Wörter zu einer Sprache gehören
   • andere Art, formale Sprache zu beschreiben