Nächste Seite: Endliche Automaten Aufwärts: Hauptseite Theorie Vorherige Seite: Wortproblem für Typ 0   Inhalt

Reguläre Sprachen

---

Unterabschnitte

• Endliche Automaten
  • Definition: Deterministischer endlicher Automat (DFA)
  • Fangzustand
  • Lauf
  • Definition: Nichtdeterministischer endlicher Automat (NFA)
  
  
• Endliche Automaten und reguläre Grammatiken
  • Übersicht
  • DFA reguläre Grammatik
  • NFA DFA (Potenzmengenkonstruktion)
  • Effizienz von NFAs
  • Reguläre Grammatik NFA
  
  
• Verknüpfungen regulärer Sprachen
  • NFAs mit -Übergängen
  • Vereinigung -
  • Durchschnitt -
  • Komplement -
  • Konkatenation -
  • Kleenabschluß -
  
  
• Algorithmen zur Feststellung von Eigenschaften
  • Das Wortproblem
  • Leerheitstest
  • Äquivalenztest
  • Endlichkeitstest
  
  
• Pumping Lemma für reguläre Sprachen
  • Definition
  • Kernaussage
  • Beweis
  • Beispiele
  
  
• Reguläre Ausdrücke
  • Syntax regulärer Ausdrücke
  • Regulärer Ausdruck NFA
  • DFA regulärer Ausdruck
  
  
• Syntaxdiagramme
  • Regulärer Ausdruck Syntaxdiagramm
  • Syntaxdiagramm DFA
  
  
• Zusammenfassung
• Minimierung von endlichen Automaten
  • Satz von Myhill & Nerode
  • Definition: Minimalautomat
  • Minimierungsalgorithmus

---