---
tags: uni-theoInf
---

# TheoInf Ex 1

## Aufgabe 1

**a)**

Man nehme ein bliebiges Wort $y$ über $\Sigma$ mit der Länge $n$ welches das Teilwort $01$ nicht beeinhaltet, so hat dieses Wort eine Anzahl $x$ weitere Wörter welche kein Teilwort $01$ enthalten.

Möchte man nun bestimmen wie viele Wörter es über dem Alphabet mit der Länge $n+1$ gibt, so hat jedes Wort $y$ zwei Möglichkeiten.

1. Nimmt man an, dass Wort endet mit $0$ kann nur ein $0$ angehänt werden ansonsten beinhaltet es das Teilwort $01$.
2. Endet das Wort mit $1$ kann entweder ein $1$ oder ein $0$ angehängt werden.

0 0 0 0

1 1 1 1
0 0 0
0 0
0

Daraus folgt, dass es über $\Sigma$ mit der Länge $n+1$ soviele zusätzliche Wörter gibt wie Wörter $y$ die mit 1 enden. Ausserdem folgt, dass die Anzahl Wörter die mit $1$ enden konstant bleibt und daraus das die Anzahl Wörter endend mit $0$ folglich um eins wächst.

Betrachtet man nun die Möglichkeiten wenn $n=0$ so ergibt sich $0$ Wörter da $|\lambda|=0$. Folglich kann festgehalten werden, dass für alle folgenden Fälle jeweils $$n+1$$ Wörter nicht das Teilwort $01$ enthalten.

**b)**

Man nehme ein bliebiges Wort $y$ über $\Sigma$ mit der Länge $n$ welches das Teilwort $00$ nicht beeinhaltet, so hat dieses Wort eine Anzahl $x$ weitere Wörter welche kein Teilwort $00$ enthalten.

Möchte man nun bestimmen wie viele Wörter es über dem Alphabet mit der Länge $n+1$ gibt, so hat jedes Wort $y$ zwei Möglichkeiten.

1. Nimmt man an, dass Wort endet mit $0$ kann nur ein $1$ angehänt werden ansonsten beinhaltet es das Teilwort $00$.
2. Endet das Wort mit $1$ kann entweder ein $1$ oder ein $0$ angehängt werden.

0 1 1 1
0
0 1

1 1 1 1
0
0 1
0 1 1
0

Daraus folgt, dass es über $\Sigma$ mit der Länge $n+1$ soviele zusätzliche Wörter gibt wie Wörter $y$ die mit 1 enden. Es wird also immer soviele zusätzliche Wörter geben wie die Anzahl der Wörter über $n$ sowie die Anzahl der Wöter über $n-1$. Diese Zahlenfolge ist auch bekannt unter der Fibonacci Folge.

Die Anzahl der Wörter ist folglich:
$$F_0 = 0, F_1 = 1$$ and
$$F_n = F_{n-1} + F_{n-2}$$

**c)**

Man nehme ein bliebiges Wort $y$ über $\Sigma$ mit der Länge $n$ welches das Teilwort $00$ sowie $01$ nicht beeinhaltet, so hat dieses Wort eine Anzahl $x$ weitere Wörter welche kein Teilwort $00$ enthalten.

Möchte man nun bestimmen wie viele Wörter es über dem Alphabet mit der Länge $n+1$ gibt, so hat jedes Wort $y$ zwei Möglichkeiten.

1. Nimmt man an, dass Wort endet mit $0$ kann nichts angehängt werden. Es ist nicht mehr Teil der möglichen Wörter in $y$.
2. Endet das Wort mit $1$ kann entweder ein $1$ oder ein $0$ angehängt werden.

Da jedes Wort endend mit 0 wieder aus der Menge der möglichen Wörter rausfliegt, wächst die Menge nicht sobald diese grösser ist als $n=0$.

Für die Menge mit $n=0$ gibt es ein Wort. Für alle $n>0$ gibt es 2 Wörter.

## Aufgabe 2

**a)**

Das Wort $a$ ist $\in ({a,b}^∗)^2$ jedoch nicht $\notin (\{a,b\}^2)^*$. Folglich ist diese Aussage widerlegt.

**b)**

Die Menge sei $L_1=\{a,b\}$ sowie $L_2=\{a\}$ dann folgt:

$$L_2 - L_1 = \emptyset $$

$$L_2 * (L_2 - L_1) = \{ab\}$$

$$L_2^2 = \{aa\}$$

$$L_2 * L_1 = \{aa,ab\}$$

$$L_2^2 - L_2 * L_1 = \emptyset $$

$$\Rightarrow L_2 * (L_2 - L_1) \neq L_2^2 - L_2 * L_1$$

## Aufgabe 3

**a)**

Sei $L=\{ab\}^*$ so gilt:

$L \not\subset \{a\}^*$ weil z.B. $\{ab\} \not\in \{a\}^*$ aber $\{ab\} \in L$
$L \not\subset \{b\}^*$ weil z.B. $\{ab\} \not\in \{b\}^*$ aber $\{ab\} \in L$
$L \neq \{a,b\}^*$ weil $\{a\} \in \{a,b\}^*$ aber $\{a\} \not\in \{ab\}^*$

$L = L^i$ da für alle $i \geq 0 \in \mathbb{N}$ gilt $\{\{ab\}^*\}^i = \{ab\}^*$

**b)**

Man nimmt das längste Element $y$ aus $L$ so existiert kein Element in $L$ sodass $y = y^2$ denn $y$ ist bereits das längste Element aus $L$. Folglich existiert keine nichtleere Menge sodass $L = L^2$.