Skip to content

2. Reguläre Sprachen, Endlicher Automat, Reguläre Grammatik

Thema 2: Reguläre Sprachen, Endlicher Automat, Reguläre Grammatik

1. Reguläre Sprachen

  • Definition: Eine reguläre Sprache ist eine formale Sprache, die von einem endlichen Automaten (DFA oder NFA) erkannt wird oder durch einen regulären Ausdruck beschrieben werden kann.

  • Beispiele:

    • Sprache aller Wörter, die nur aus "a" und "b" bestehen und mit "ab" enden: (a|b)*ab

    • Sprache aller Wörter mit einer geraden Anzahl von "0": (00)*

    • Besteht aus:

      • Q: Menge der Zustände

      • Σ: Eingabealphabet

      • δ: Übergangsfunktion (jedes Zeichen führt zu genau einem Zustand)

      • q₀: Startzustand

      - F: Menge der Endzustände (akzeptierende Zustände)

      2. Endliche Automaten (Finite Automata)

2.1 Deterministischer Endlicher Automat (DFA)

  • Eindeutige Übergänge:
    Für jedes Symbol des Alphabets gibt es genau einen definierten Übergang pro Zustand.

    • Beispiel:
      Wenn du in Zustand B bist und ein b liest, gibt es nur einen Weg, z.B.:

      B --b--> C

  • Klare Pfade:
    Es gibt immer genau einen Pfad, den der Automat bei einer bestimmten Eingabe verfolgt.

    • Akzeptanz: Ein Wort wird akzeptiert, wenn dieser eindeutige Pfad in einem Endzustand endet.
    • Denkweise: Keine Verzweigungen, keine Unsicherheit. Es gibt nur einen möglichen Ablauf für jedes Wort.

2.2 Nichtdeterministischer Endlicher Automat (NFA)

  • Mehrere Möglichkeiten:
    Für das gleiche Eingabesymbol kann es mehrere mögliche Übergänge geben.

    • Beispiel:
      Aus Zustand B kannst du mit dem Symbol b sowohl nach A als auch nach C gelangen:

      B --b--> A B --b--> C

  • „Parallele Wege“:
    Der Automat „probiert“ alle möglichen Wege gleichzeitig aus (theoretisch betrachtet).

    • Akzeptanz: Ein Wort wird akzeptiert, wenn mindestens ein Weg in einen Endzustand führt.
    • Denkweise: Stelle dir vor, der Automat „klont“ sich bei jeder Verzweigung und jeder Klon versucht seinen eigenen Weg.
    • Epsilon-Übergänge (ε):
      NFAs können auch Übergänge haben, bei denen kein Eingabesymbol gelesen wird, z.B.

    A --ε--> B

3. Reguläre Grammatiken

  • Definition: Eine Grammatik, die reguläre Sprachen beschreibt.

  • Form: Produktionsregeln der Art:

    • Rechtslineare Grammatik: A → aB oder A → a

    • Linkslineare Grammatik: A → Ba oder A → a

Beispiel:

S → aS | bA
A → b

Akzeptiert: "ab", "aab", "aaab", ...

4. Typische Prüfungsaufgaben

  • Erkennen von Wörtern durch Automaten: Prüfen, ob ein Wort von einem DFA/NFA akzeptiert wird.

  • Umwandeln von Automaten in reguläre Grammatiken: Jeder Übergang wird zu einer Produktionsregel.

  • Umwandeln von Grammatiken in Automaten: Zustände repräsentieren Variablen der Grammatik.EndlicheAutomaten.png