AFS UE 01

Task 3

$|\Sigma |=$ size of $\Sigma$
$ϵ$ is the word of length 0. ($|ϵ|=0$)

$\Sigma =\{a,b,c\}$
$|\Sigma |=3$
$i\text{updelta}n=3$
$|\Sigma {|}^3=27$

Initiation

There are $|\Sigma |$ many words of length 1 over $\Sigma$.
There is one word of length 0 over $\Sigma$.

Induction Step

$\forall n\in \mathbb{N}$, there are $|\Sigma {|}^n$ words of length $n$ over $\Sigma$.
$S_n$ the set of words over $\Sigma$ of length n.
$S_{n+1}$ the set of words over $\Sigma$ of length n + 1.

$f:\Sigma \times S_n\to S_{n+1}$
if f is injektiv and surjektiv then
$|S_{n+1}|=|\Sigma \times S_n|=|\Sigma |\times |S_n|$
$|S_{n+1}|=|\Sigma |\times |\Sigma {|}^n=|\Sigma {|}^{n+1}$

if you have a word of length n
if you have a word of length n+1
then $w=x{w}^{\prime }$ where $x\in \Sigma$ and $w^{\prime }\in S_n$
$S_{n+1}=|\Sigma |\times S_n=|\Sigma {|}^{n+1}$

Task 4

number of a’s in $w=|w{|}_a$

Initiation

For w of length 0, we have $w=ϵ=ϵϵ$ and $|u{|}_a=0=|v{|}_b$

Induction Step

the induction hypothesis is true for $n\in \mathbb{N}$
Let w of length n+1 $(w\in {\Sigma }^{n+1})$
if $w=bw’=bu’v’$ with $|u’{|}_a=|v’{|}_b$ → $u=bu’$ $v=v’$
if $w=aw’=au’v’$ with $|u’{|}_a=|v’{|}_b$ →

$u’=ϵ$ then $w=av’$ → $v=av’$ $|u{|}_a=0=|v{|}_b$

Task 5

There is a $\Sigma$. There is a Funtion r.
$\forall v,w\in {\Sigma }^{\ast }:r(vw)=r(w)r(v)$

$n=|v|+|w|n\in \mathbb{N}$

Initiation

For $n=0$ are $v,w=ϵ$
$r(ϵϵ)=r(ϵ)=ϵ=ϵϵ=r(ϵ)r(ϵ)$

Induction Step

the induction is true for $n\in \mathbb{N}:n>0$
if $r(vw)=r(v)r(w)$ for $|v|+|w|=n$
for $n+1$ → $|v’|=|v|+1$ or $|w’|=|w|+1$

if $|v’|=|v|+1$
$v’=vx$ $x\in \Sigma$
$r(v’)=r(vx)=xr(v)$
$r(v’w)=r(vxw)=r(w)xr(v)=r(w)r(v’)$

if $|w’|=|w|+1$
$w’=wx$ $x\in \Sigma$
$r(w’)=r(wx)=xr(w)$
$r(vw’)=r(vwx)=xr(w)r(v)=r(w’)r(v)$

Task 6

siehe notizen