Definitionen

• Bezeichnungen
  • \(\varSigma\)
  • \(\varsigma\)
  • \(\varSigma^*\)
  • Verkettung
  • Wortmenge / formale Sprache in \(P(\varSigma^*)\)
• Transitionssysteme, endl. Automaten
  • Transitionssystem
  • nicht - deterministischer endlicher Automat
  • Pfad
  • Akzeptiert
  • Sprache
  • Deterministisch
  • Präfix
  • Suffix
  • Infix
• Produktautomat
• NEA mit Worttransitionen
  • Sonderfall: \(\varepsilon\)-NEA
• Deterministisch endlicher Automat (DEA)
• Fortsetzung
• \(\delta^*(p,w) = q \Longleftrightarrow a: p \rightarrow^w q\)
  • Beweis
  • Bemerkung b
  • Schreibweise
• Regulär
• Lemma: Ist \(L \subset \varSigma^*\) von DEA erkennbar, so auch \(\varSigma \backslash L\)
  • Beweis:
  • Folgerung:
• Beschränkung auf erreichbare Zuständen
  • Definition
• Äquivalenzklassen
  • Bemerkungen
• Reduzierter DEA
  • Zu jedem DEA existiert ein äquivalenter reduzierter
  • Der DEA a ist ein Automat mit minimaler Angabe von Zuständen (der L(a) erkennt)