Reguläre Sprachen

• Typ 3 formale Sprache
• equivalent zu regulären Ausdrücken & deterministischen und nichtdeterministischen endlichen Automaten

Wann ist eine Sprache regulär?

• wird von Regulärer Grammatik erzeugt
• wird von endlichem Automat akzeptiert
• kann durch einen regulären Ausdruck dargestellt werden

Definition

$$\begin{array}{rl}L& =\text{Sprache}\\ L& \subseteq {\Sigma }^{\ast }\end{array}$$

Mitschrift aus der Stunde

In den Produktionsregeln sind nur folgende Regeln erlaubt:

• ein Nicht-Terminal wird durch genau ein Terminal ersetzt ($NT\to T$)
  • genau ein Terminalsymbol $X\to aY$
• ein Nicht-Terminal wird durch genau ein Nicht-Terminal und genau ein Terminal ersetzt \begin{align} NT &\rightarrow T \text{ } NT &\text{rechtsregulär} \\ NT &\rightarrow NT \text{ } T &\text{linksregulär} \end{align}
  • maximal ein Nichtterminal

---

$a,X:\text{Nichtterminalsymbol},Y:\text{Terminalsymbol}$

Wichtig

Es müssen immer ALLE Regeln einheitlich entweder links- oder rechtsregulär sein!