\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage{cancel}
\usepackage{eurosym}

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 10}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Do, 11-13 Uhr, Vasileios Anastasatos
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\eur}{\mbox{\euro}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
Es gilt: $L_X \cap L_Y \neq \emptyset$ genau dann wenn
$$I=J \AND J=K \AND K=H \mbox{ und somit auch } H=I$$
Außerdem muss gelten:
$$X[I]=Y[H]=Y[I]$$
Es folgt: Worte aus $L_X \cap L_Y$ haben folgende Form:
$$\{I^R \# I \$ I^R \# X[I] \; | \; I \in \{1,...,k\}^+\}$$
Da $X[I^n]=Y[I^n] \forall n \geq 1$ (wegen \textsf{PCP}) wenn $X[I]=Y[I]$ gilt folgt
$$L_X \cap L_Y = \{I^{R^n} \# I^n \$ I^{R^k} \# X[I^n] \; | \; I \in \{1,...,k\}^+\} \mbox{ mit } n \geq 1$$
Es bleibt zu zeigen, dass $L_X \cap L_Y$ nicht kontextfrei ist. \\
Beweis mit dem Pumping Lemma:
\begin{enumerate}
	\item Gegner gibt ein $N \in \SetN$ vor.
	\item Ich wähle $z \in L_X \cap L_Y$ mit $|z| \geq N:$
		$$z=I^{R^N} \# I^N \$ I^{R^N} \# X[I^N]$$
	\item Gegner gibt eine Unterteilung $z=uvwxy$ mit $|vwx| \leq N$ und $|vx| > 0$ vor.
	\item Ich wähle $i=0$: $uwy \notin L_X \cap L_Y$ da
		\begin{enumerate}[1.]
			\item Fall: $vx$ enthält ein \# oder \$: $uwy$ kann nicht mehr aus $L_X \cap L_Y$ sein, da \# oder \$ fehlt.
			\item Fall: $vx$ enthält weder \# noch \$: $uwy$ kann nur ein Teilstring von $\underbrace{I^{R^N}}_{=:a^R}$, $\underbrace{I^N}_{=:a}$ oder $\underbrace{X[I^N]}_b$ sein. Durch Wegfallen von $vx$ wird die Länge von $a^R$, $a$ oder $b$ in $uwy$ verkürzt, somit ist $uwy \notin L_X \cap L_Y$. \\
			Für ein Wort $a^R \# a \$ a^R \# b \in L_X \cap L_Y$ muss gelten $|a^R| = |a| = |b|$.
		\end{enumerate}
\end{enumerate}

\newpage
\section*{Aufgabe 2}
Betrachte folgende Sprache:
$$L_P = \{I \# X[I]^R \$ Y[I] \# J^R \; | \; I,J \in \{1,...,k\}^+\}$$
wobei $k,X,Y$ eine Instanz des \textsf{PCP}. Eine kontextfreie Grammatik für $L_P$ ist:
$$G_P = (\Sigma \cup \{\$,\#\} \cup \{1,...,k\}, \{S,L,R\},S,P)$$
mit Produktionen
\begin{align*}
	S &\to L \$ R \\
	L &\to i L(x_i)^R \\
	L &\to i \# (x_i)^R \\
	R &\to (y_i)Rj \\
	R &\to (y_i)\#j
\end{align*}
wobei $1 \leq i \leq k$ und $1 \leq j \leq k$. \\
Gibt es ein Palindrom in $L_P$, so gilt $X[I]=Y[I]$ und $I=J$. Dann hat \textsf{PCP} eine Lösung für diese Instanz. Gibt es kein Palindrom in $L_P$, so hat auch \textsf{PCP} keine Lösung für diese Instanz. \\[0.5cm]
Insgesamt folgt:\\
Es ist nicht entscheidbar, ob eine gegebene kontextfreie Grammatik eine Sprache generiert, die ein Palindrom positiver Länge enthält, sonst wäre $L_P$ und somit \textsf{PCP} entscheidbar.

\newpage
\section*{Aufgabe 3}
Seien $f,g \in \mathsf{F"UP}$. \\
Behauptung:
$$f \notin \OnotO(g) \not\Leftrightarrow f \in \omega(g)$$
Beweis durch Gegenbeispiel: \\
Wähle
\begin{align*}
	f(n) &= (1+(-1)^n)n+1 \\
	g(n) &= 1 \\[0.5cm]
	\OnotO(g) &= \{f \in \mathsf{F"UP} \; | \; \exists c > 0: f \leq_{f"u} c \cdot g\} \\
	\Leftrightarrow \OnotO(g) &= \{f \in \mathsf{F"UP} \; | \; \exists c > 0: \exists n_0 \in \SetN, \forall n \geq n_0: f(n) \leq c \cdot g(n)\} \\
	\Rightarrow \neg \OnotO(g) &= \{f \in \mathsf{F"UP} \; | \; \forall c > 0: \forall n_0 \in \SetN, \exists n \geq n_0: f(n) > c \cdot g(n)\} \\[0.3cm]
	\omega(g) &= \{f \in \mathsf{F"UP} \; | \; \forall c > 0: \exists n_0 \in \SetN: \forall n \geq n_0: f(n) \geq c \cdot g(n)\}
\end{align*}
Es gilt also $f \notin \OnotO(g)$, oder anders geschrieben $f \in (\neg \OnotO(g))$.
\begin{align*}
	f(n) &> c \cdot g(n) \\
	\Leftrightarrow (1+(-1)^n)n+1 &> c \cdot 1 \\
\end{align*}
$$\Leftrightarrow \begin{cases}2n+1>c & \mbox{falls } n \mbox{ gerade} \\ 1 > c & \mbox{falls } n \mbox{ ungerade}\end{cases}$$
Es gilt jetzt: $\forall c > 0, \forall n_0 \in \SetN, \exists n \geq n_0: 2n+1>c$. \\
Wähle für $n$ immer eine gerade Zahl mit $\displaystyle n \geq n_0, n > \frac{c-1}{2}$. \\
Es gilt $f \notin \omega(g)$:
\begin{align*}
	f(n) &\geq c \cdot g(n) \\
	\Leftrightarrow (1+(-1)^n)n+1 &\geq c \cdot 1
\end{align*}
$$\Leftrightarrow \begin{cases}2n+1 \geq c & \mbox{falls } n \mbox{ gerade (1)} \\ 1 \geq c & \mbox{falls } n \mbox{ ungerade (2)}\end{cases}$$
\begin{enumerate}[(1)]
	\item stimmt: $\forall c > 0 \exists n_0 \in \SetN, \forall n \geq n_0: 2n+1 \geq c$. Wähle $\displaystyle n_0 \geq \frac{c-1}{2}$.
	\item stimmt nicht für alle $c > 0$ bzw. $n \geq n_0$.
\end{enumerate}

\end{document}