# Blatt 5

## Aufgabe 1

$S \rightarrow ASB$
$A \rightarrow aAS | a | \epsilon$
$B \rightarrow SbS | A | bb$

1. Entferne $\epsilon$-Produktionen:
$S \rightarrow ASB | SB$
$A \rightarrow aAS | a | aS$
$B \rightarrow SbS | A | bb$
2. Erzeuge Variablen für Terminale:
$S \rightarrow ASB | SB$
$A \rightarrow CAS | C | CS$
$B \rightarrow SDS | A | DD$
$C \rightarrow a$
$D \rightarrow b$
3. Verkürze Produktionen mit langen rechten Seiten:
$S \rightarrow AF | SB$
$A \rightarrow CG | C | CS$
$B \rightarrow SH | A | DD$
$C \rightarrow a$
$D \rightarrow b$
$F \rightarrow SB$
$G \rightarrow AS$
$H \rightarrow DS$

## Aufgabe 2

a)
$S \rightarrow aA | bB$
$A \rightarrow aB | b$
$B \rightarrow bA | aC$
$C \rightarrow aS | aB | bC$


b)

Sei $G=(V,\Sigma, P,S)$ eine Typ-3 Grammatik mit V Menge der nicht terminal Symbole, $\Sigma$ Menga der Terminalsymbole, P Menge der Produktionsregeln und S die Startproduktionsregel. Da G Typ-3 Grammtik gilt:

1. Kontextsensitivität: $\forall w_1 \rightarrow w_2 \in P: |w_1| \leq |w_2|$
2. Kontextfreiheit: $\forall w_1 \rightarrow w_2 \in P: w_1 \in V$ minimal (einzelne Variable)
3. Regularität: $\forall w_1 \rightarrow w_2 \in P: w_2 \in \Sigma \cup \Sigma V$

z.z. Jede Typ-3 Sprache ist regulär d.h. Die Menge aller regulären Sprachen ist gleich der Menge aller Typ-3 Sprachen

$"\supseteq"$: Gezeigt in Vorlesung

$"\subseteq"$:

Definiere NEA $M = (Q,\Sigma_M,\delta,s, F)$ mit $Q = V$, $\Sigma_M = \Sigma$, $s = S$.

> Da obriges $G$ von Typ-3 gilt für jede Produktionsregel aus P, dass sie von entwerder von der Form $A \rightarrow BC$ oder $B \rightarrow b$ wobei $A,B,C \in V \space bzw. Q$ und $a \in \Sigma \space bzw. \Sigma_M$.

Konstruiere $\delta$ folgendermaßen:

$\forall w_1 \rightarrow w_2 \in P$ definiere $\delta(A, b) = C$

Daraus folgt, dass zu jeder Typ-3 Grammatik $G$ ein nicht determinstischer endlicher Automat $M$ generierbar ist für den gilt, dass $L(G) = L(M)$. Da M einlich ist folgt dass auch $L(M)$ regulär sein muss. $\square$

## Aufgabe 3

a) $L_1 = \{a^nb^{2n}c^m|n,m \geq 1\}$
Behauptung: $L_1$ ist Typ-2-Sprache.
Beweis:
- Zeige: $L_1$ ist mindestens Typ-2-Sprache.

Erstellung eines Kellerautomaten, der $L_1$ akzeptiert:
Definiere $E:= \epsilon$.


- Zeige: $L_1$ ist keine Typ-3-Sprache.

b) $L_2 = \{a^nb^{2n}c^m|1 \leq n \leq 3, m \leq 0\}$
Behauptung: $L_2$ ist Typ-3-Sprache.
Beweis: Erstellung eines DEAs, der $L_2$ akzeptiert: