Reguläre Sprachen

rechtslinear, rekursiv definiert,

• Eine Produktion heißt rechtslinear genau dann, wenn auf der linken Seite ein Nichtterminalssymbol steht und die rechte Seite folgende Gestalt hat:
  • ein Terminalsymbol gefolgt von einem Nichtterminalsymbol oder
  • ein Terminalsymbol.
    alternativ:
  • ein Terminalsymbol gefolgt von einem Nichtterminalsymbol oder
  • das leere Wort.

• Eine Grammatik heißt rechtslinear / regulär genau dann, wenn alle Produktionen der Grammatik rechtslinear sind.

• Zu jedem endlichen Automaten gibt es eine rechtslineare Grammatik, mit der die Sprache dess Automaten erzeugt werden kann. - und - Zu jeder rechtslinearen Grammatik gibt es einen nichtdeterministischen endlichen Automaten, der die von der Grammatik erzeugt Sprache erkennt. (Äquivalenzsatz) - Zu jedem nichtdeterministischen endlichen Automaten gibt es einen deterministischen endlichen Automaten, der dieselbe Sprache erkennt. - Zu jedem nichtdeterministischen endlichen Automaten gibt es einen deterministischen endlichen Atuomaten, der dieselbe Sprache erkennt.

• Satz von Kleene: Jede durch einen endlichen Automaten erkennbare Sprache kann durch einen regulären Ausdruck beschrieben werden.
  Jede durch einen regulären Ausdruck beschreibbare Sprache kann durch einen endlichen Automaten erkannt werden.

• Eine Sprache heißt regulär genau dann, wenn sie durch einen regulären Ausdruck dargestellt werden kann.
• Eine Sprache ist reguläŕ genau dann, wenn sie
  • durch einen regulären Ausdruck dargestellt werden kann /
  • von einem deterministischen endlichen Automaten erkannt werden kann /
  • von einem nichtdeterministischen endlichen Automaten erkannt werden kann /
  • von einer rechtslinearen Grammatik erzeugt werden kann.

• Bei der Umwandlung einer rechtslinearen Grammatik in einen endlichen Automaten kann ein sogenannter nichtdeterministischer Automat entstehen. Von einem Zustand aus können bei gleicher Eingabe Übergänge in verschiedene Zustände erfolgen.