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

## Übung 1
Betrachten Sie folgendes algorithmisches Problem:

**Bestimmung des Nerode-Index**
- **Eingabe**: ein (vollständiger) NEA $N$
- **Ausgabe**: der Nerode-Index der Sprache $L(N)$

Beschreiben Sie eine algorithmische Lösung dieses Problems (stichpunktartig oder als Pseudocode).
Nutzen Sie dazu das in der Vorlesung gesammelte Wissen und begründen Sie damit die Durchführbarkeit und Korrektheit Ihrer Lösung.

**Lösung:**

- Potenzautomat bilden
- DEA minimieren
- Zustände zählen

## Übung 2
Betrachten Sie den Automaten $A$ aus Abbildung 1 über dem Alphabet $\Sigma = \{0,1\}$.
![image_864.png](image_864.png)

### 2(a)
Wenden Sie das in den Vorlesungsfolien beschriebene Verfahren zur Minimierung des Automaten $A$ an, um die Zustands-Äquivalenzklassen des Automaten $A$ zu bestimmen.
Stellen Sie Ihr Vorgehen nachvollziehbar dar (orientieren Sie sich dazu an dem finalen Beispiel des Foliensatzes 4).

- Äquivalenzklassen finden
  - {a,b,c,d,h,f}, {e,g}
    - Zeuge: ε
  - {a,c,d,f}, {b,h}, {e,g}
    - Zeuge: 1
  - {a,d,c}, {f}, {b,h}, {e,g}
    - Zeuge: 01
  - {a,c}, {d}, {f}, {b,h}, {e,g}
    - Zeuge: 11
  - {a,c}, {d}, {f}, {b}, {h}, {e,g}
    - Zeuge: 001

- Zustandsübergänge
  - $≡_{a,c}$
    - 1 → $≡_{d}$
    - 0 → $≡_{b}$
  - $≡_{d}$
    - 0,1 → $≡_{b}$
  - $≡_{b}$
    - 0 → $≡_{a,c}$
    - 1 → $≡_{e,g}$
  - $≡_{e,g}$
    - 0 → $≡_{f}$
    - 1 → $≡_{h}$
  - $≡_{h}$
      - 0 → $≡_{f}$
      - 1 → $≡_{e,g}$
  - $≡_{f}$
      - 0, 1 → $≡_{f}$

### 2(b)
Konstruieren Sie den Quotientenautomaten zu $A$ mit Hilfe der von Ihnen bestimmten Zustands-Äquivalenzklassen (in der Graphdarstellung).

```plantuml
@startuml
scale 0.50

left to right direction
skinparam dpi 150

skinparam state {
    BackgroundColor #FFFACD
    BorderColor black
    FontName Helvetica
    RoundCorner 30
    Shadowing false
    LineThickness 0
}


state eg##[bold]

[*] --> ac
ac --> d: 1 
ac --> b: 0
d --> b: 0,1
b --> ac: 0
b --> eg: 1
eg --> h: 1
eg --> f: 0
h --> eg: 1
h --> f: 0
f --> f: 0,1


@enduml
```


## Übung 3
Betrachten Sie die beiden deterministischen endlichen Automaten $A_1$ und $A_2$ aus Abbildung 2.
Lesen Sie Kapitel 2.3.3 über das Äquivalenzproblem für endliche Automaten aus dem Skript.
Nutzen Sie das dort beschriebene Vorgehen, um nachvollziehbar zu überprüfen, ob die Automaten $A_1$ und $A_2$ die gleiche Sprache akzeptieren.

![image_865.png](image_865.png)




## Übung 4
### 4(a)
Geben Sie die folgende Grammatik $G_1$ in formaler Tupel-Darstellung an.
Leiten Sie außerdem 5 Wörter der Sprache $L(G_1)$ ab und beschreiben Sie anschließend $L(G_1)$ in formaler Mengenschreibweise.

Grammatik $G_1$:
- $S \Rightarrow aSa\ |\ bSb\ |\ X$
- $X \Rightarrow 0\ |\ 1$

  - $ Σ = \{a, b\}$
  - $V = \{S, X\}$
  - $S ∈ V$
  - $R = \{S \Rightarrow aSa \mid bSb \mid X, X \Rightarrow 0 \mid 1\}$


1. $S \Rightarrow aSa \Rightarrow aaSaa \Rightarrow aaXaa \Rightarrow aa0aa$
2. $S \Rightarrow bSb \Rightarrow bbSbb \Rightarrow bbXbb \Rightarrow bb1bb$
3. $S \Rightarrow aSa \Rightarrow abSba \Rightarrow abXba \Rightarrow ab0ba$
4. $S \Rightarrow aSa \Rightarrow aaSaa \Rightarrow aaXaa \Rightarrow aa1aa$
5. $S \Rightarrow aSa \Rightarrow aXa \Rightarrow a0a$

Die Sprache $L(G_1)$ besteht aus Wörtern, die mit einer beliebigen Anzahl von `a`s und `b`s beginnen und (in umgekehrter Reihenfolge) enden, wobei
zwischen den äußeren Zeichen ein Wort aus $\{0, 1\}$ steht.

### 4(b)
Geben Sie die folgende Grammatik $G_2$ in formaler Tupel-Darstellung an.
Leiten Sie außerdem 5 Wörter der Sprache $L(G_2)$ ab und beschreiben Sie anschließend $L(G_2)$ in formaler Mengenschreibweise.

Grammatik $G_2$:
- $S \Rightarrow A00A$
- $A \Rightarrow 0A\ |\ 1A\ |\ 0\ |\ 1$

- $ Σ = \{0, 1\}$
- $V = \{S, A\}$
- $S ∈ V$
- $R = \{S \Rightarrow A00A, A \Rightarrow 0A \mid 1A \mid 0 \mid 1\}$


1. $S \Rightarrow A00A \Rightarrow 1A00A \Rightarrow 10A00A \Rightarrow 100A00A \Rightarrow 1000A00A \Rightarrow 10001$
2. $S \Rightarrow A00A \Rightarrow 0A00A \Rightarrow 00A00A \Rightarrow 000A00A \Rightarrow 0000A00A \Rightarrow 00001$
3. $S \Rightarrow A00A \Rightarrow 1A00A \Rightarrow 10A00A \Rightarrow 100A00A \Rightarrow 1000A00A \Rightarrow 10000A00A \Rightarrow 100001$
4. $S \Rightarrow A00A \Rightarrow 0A00A \Rightarrow 00A00A \Rightarrow 000A00A \Rightarrow 0001A00A \Rightarrow 00010A00A \Rightarrow 0001001$
5. $S \Rightarrow A00A \Rightarrow 1A00A \Rightarrow 10A00A \Rightarrow 100A00A \Rightarrow 1000A00A \Rightarrow 10001A00A \Rightarrow 1000100$

Die Sprache besteht aus Wörtern, die aus einem Wort $A$ gefolgt von `00` und dann wieder dem Wort $A$ bestehen, wobei $A$ eine beliebige Kombination von `0`s und `1`s ist.
Formale Mengenschreibweise: 
$L(G_2) = \{x00y \mid x, y \in \{0, 1\}^*\}$

### 4(c)
Geben Sie alle möglichen Ableitungen mit Regeln aus der Grammatik $G_2$ für das Wort $10001$ an.

1.
   - $S \Rightarrow A00A$
   - $A \Rightarrow 1A$ (1A00A)
   - $A \Rightarrow 0$ (1000A)
   - $A \Rightarrow 1$ (10001)
2. 
   - $S \Rightarrow A00A$
   - $A \Rightarrow 0A$ (A000A)
   - $A \Rightarrow 1$ (1000A)
   - $A \Rightarrow 1$ (10001)

## Übung 5
Betrachten Sie folgende Grammatik $G$:
- $S \Rightarrow x\ |\ yS$
- $xy \Rightarrow yx$
- $yx \Rightarrow xy$

### 5(a)
Können Sie mit $G$ das Wort $xxy$ ableiten?
- Nein, mit der Grammatik $G$ kann das Wort $xxy$ nicht abgeleitet werden.
- Begründung:
  - Die Regel $xy \Rightarrow yx$ oder $yx \Rightarrow xy$ erlaubt es nicht, ein `x` vor einem `y` zu platzieren, wenn bereits ein `y` abgeleitet wurde.

Können Sie mit $G$ das Wort $xyy$ ableiten?
- Ja, mit der Grammatik $G$ kann das Wort $xyy$ abgeleitet werden.
- Begründung:
  - Die Ableitung erfolgt durch die Regel $S \Rightarrow yS$, gefolgt von der Regel $S \Rightarrow x$, was zu $xyy$ führt.

### 5(b)
Beschreiben Sie die von $G$ erzeugte Sprache in formaler Mengenschreibweise.

$L(G) =\{w ∈\{x,y\}^* \mid  \#_X(w)=1}}

### 5(c)
Gibt es eine Grammatik $G'$ mit $L(G') = L(G)$, sodass $G'$ weniger als vier Regeln hat?

- Ja, es gibt eine Grammatik $G'$ mit $L(G') = L(G)$, die weniger als vier Regeln hat.
  - Man kann die Regel $xy → yx streichen, da das x immer am Ende folgt und somit nur die Regel $yx → xy$ benötigt wird.