====== 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.