# Übungsblatt 7
> Wenzel Schwan (1125033), Paul Kneidl (1125219), David Schirrmeister (1125746), Michelle Klein (1126422)

## Übung 1
Betrachten Sie folgende Grammatik:  
$$
G : \quad S \Rightarrow abSc \mid bT \\
T \Rightarrow bT \mid bU \\
U \Rightarrow b \mid c
$$

### 1(a)
Geben Sie Ableitungen (Folge von 1-Schritt-Ableitungen) für jedes der folgenden Wörter an:  

- (i) $$w_1 = bbbc$$
    - $S → bT → bbT → bbbU → bbbc$
- (ii) $$w_2 = ababbbbcc$$
    - $S → abSc → ababScc → ababbTcc → ababbbUcc → ababbbbcc$
- (iii) $$w_3 = abbbcc$$
    - $S → abSc → abbTc → abbbUc → abbbcc$


### 1(b)
Welche Sprache wird von Grammatik $G$ erzeugt?

Wörter, die mit beliebig vielen $ab$ beginnen, gefolgt von einer beliebigen Anzahl von $b$ und enden mit einer beliebigen Anzahl von $c$, mindestens aber so viele, wie a, maximal eins mehr.

## Übung 2
### 2(a)
Geben Sie für jede der folgenden Sprachen eine Grammatik mit höchstens 7 Regeln an, welche die jeweilige Sprache erzeugt, und begründen Sie die Korrektheit Ihrer Grammatik.  

- (i) $$L_1 = \{ w \in \{0,1\}^* \mid w \text{ ist ein Palindrom mit durch 4 teilbarer Länge} \}$$
  - $S → 00S00 | 01S10 | 10S01 | 11S11 | ε$
- (ii) $$L_2 = \{ w \in \{0,1\}^* \mid \#1(w) \geq \#0(w) \}$$
    - $S → 1A | 0B | ε$
    - $A → 1A | 0S | ε$
    - $B → 1A$
- (iii) $$L_3 = \{ w \in \{0,1\}^* \mid \#0(w) \leq 2 \}$$
  - $S → 1S | 0A | ε$
  - $A → 1A | 0B | ε$
  - $B → 1B | ε$


## Übung 3
In den Vorlesungsfolien zu „Kapitel 5: Grundlagen formaler Grammatiken“ finden Sie die kontextfreie Grammatik $G_{\text{Tags}}$.  
Diese benutzt mehrere $\varepsilon$-Regeln der Form $V \Rightarrow \varepsilon$ für Variablen $V$.

Passen Sie die Grammatik $G_{\text{Tags}}$ so an (ohne die erzeugte Sprache zu ändern), dass $G_{\text{Tags}}$ weiterhin kontextfrei ist und $S \Rightarrow \varepsilon$ die einzige $\varepsilon$-Regel ist.  
**Hinweis:** Es reicht, das Vorgehen zu beschreiben. Eine vollständige Neudefinition der Grammatik ist nicht notwendig (aber erlaubt).

S zu $S → S' | ε$ ändern, wobei $S'$ eine neue Variable ist, die alle Regeln von $S$ außer der Regel $S \Rightarrow \varepsilon$ enthält.
In den restlichen Regeln das ε durch ein S' ersetzen, sodass die Regeln nur noch auf S' enden. Dadurch können beliebig viele Elemente hinzugefügt werden, ohne dass die Grammatik ihre kontextfreie Eigenschaft verliert und S → ε ist die einzige ε-Regel.

## Übung 4
Vergleichen Sie die Definition von **regulären Grammatiken** aus den Vorlesungsfolien (Definition 5.5) mit der Definition von **rechtslinearen Grammatiken** aus dem Skript (Definitionen 3.6 und 3.7), indem Sie folgende Fragen beantworten:

### 4(a)
Beschreiben Sie in eigenen Worten, worin sich beide Definitionen unterscheiden.  

Eine reguläre Grammatik erlaubt Produktionen der Form:
- rechtslinear: A→aB oder A→a
- linkslinear: A→Ba oder A→a
- Oder eine Kombination aus beiden – also: entweder links- oder rechtslinear, gemischt erlaubt.

Eine rechtslineare Grammatik erlaubt nur Produktionen der Form:
- A→aB oder A→aA
- d.h. Nichtterminale dürfen nur ganz rechts stehen, es ist keine Mischung oder Linkslinearität erlaubt.

### 4(b)
Geben Sie eine Grammatik an, die nach diesen Definitionen regulär, aber nicht rechtslinear ist.  

$S → aS | Sb | ε$


### 4(c) (Diskussionsaufgabe für die Präsenzübung)
Bereiten Sie diese Aufgabe vor, indem Sie in Ihrer Abgabegruppe darüber diskutieren.  
Sie müssen für diese Teilaufgabe **keine schriftliche Lösung abgeben** (machen Sie sich aber ruhig Notizen für die Diskussion in der Präsenzübung).

Betrachten Sie die Definition einer regulären Sprache (Definition 5.10) und die Definition einer rechtslinearen Sprache (Definition 3.8):

- (i) Erklären Sie, warum jede **rechtslineare Sprache** auch **regulär** ist.
  - Struktur entspricht Übergangsfunktion eines endlichen Automaten, daher ist jede rechtslineare Sprache auch regulär.
  - Man kann einen äquivalenten DEA konstruieren, der die gleiche Sprache akzeptiert.
- (ii) Erklären Sie, warum jede **reguläre Sprache** auch **rechtslinear** ist.
  - Jede reguläre Sprache wird von einem DEA akzeptiert
  - Zu jedem DEA kann man eine rechtslineare Grammatik konstruieren
    - Zustände = Nichtterminale
    - Übergänge = Produktionen der Form A → aB
    - Akzeptierende Zustände = Produktionen der Form A → a oder A → ε



## Übung 5
Betrachten Sie folgende Grammatik:  
$$
G: \quad S \Rightarrow ABS \mid ACS \mid \varepsilon \\
AB \Rightarrow BA,\quad AC \Rightarrow CA,\quad BC \Rightarrow CB \\
A \Rightarrow a,\quad B \Rightarrow b,\quad C \Rightarrow c
$$

### 5(a)
Leiten Sie nachvollziehbar die Wörter  
$$w_1 = abac,\quad w_2 = cbaa,\quad w_3 = baba,\quad w_4 = bbbaaaac$$  
ab.

- abac
  - $S → ABS → ABACS → ABAC → aBAC → abAC → abaC → abac$
- cbaa
  - $S → ACS → ACABS → ACAB → CAAB → CABA → CBAA → cBAA → cbAA → cbaA → cbaa$
- baba
  - $S → ABS → ABABS → ABAB → BAAB → BABA → bABA → baBA → babA → baba$
- bbbaaaac
  - $S → ABS → ABABS → ABABABS → ABABABACS → ABABABAC → ABABBAAC → ABBABAAC → ABBBAAAC → BABBAAAC → BBABAAAC → BBBAAAAC → ... → bbbaaaac$
    - ... = $A → a, B → b, C → c$

### 5(b)
Wie lautet die von $G$ erzeugte Sprache $L(G)$?

Die von $G$ erzeugte Sprache $L(G)$ besteht aus Wörtern, die aus den Buchstaben $a$, $b$ und $c$ bestehen und in denen die Buchstaben in beliebiger Reihenfolge angeordnet sind, solange die Anzahl der Buchstaben $a$ = $b$ + $c$ ist.

### 5(c)
Die gezeigte Grammatik ist nach der Definition aus der Vorlesung (siehe Folien) **nicht kontextsensitiv**. Erklären Sie weshalb.  

Da auf der rechten Seite ebenfalls die Startvariable $S$ vorkommt, ist die Grammatik nicht kontextsensitiv.

### 5(d) (Bonusaufgabe)
Wandeln Sie die Grammatik $G$ in eine **kontextsensitive Grammatik** $G'$ um, so dass $$L(G') = L(G)$$ gilt.

**Hinweis:**  
Überlegen Sie sich zunächst, **welche Regeln die Kontextsensitivität verletzen**.  
Ersetzen Sie diese Regeln dann jeweils durch eine oder mehrere neue Regeln (ggf. mit neuen Variablen), die **kontextsensitiv sind** und denselben Effekt erzielen.