\documentclass[12pt]{article}

\usepackage{a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{gastex}
\usepackage{ngerman}
\usepackage{qtree}

\title{\textsc{Einführung in die Computerlinguistik \\ \large Übung 7}}
\author{\shortstack[c]{Jan Hendrik Dithmar \\ \footnotesize Matrikelnummer 2031259}}
\date{}

\pagestyle{fancy}

\lhead{Übung 7}
\chead{}
\rhead{Dithmar (2031259)}
\lfoot{Einf. i. d. Computerlinguistik}
\cfoot{Seite \thepage}
\rfoot{WS 2006/2007}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\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{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\pfr}{\ensuremath{\rightarrow} }
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}
\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}

\section*{Aufgabe 7.1}
\subsection*{(a)}
\begin{tabular}{ll}
	NP \pfr ART NN & NP \pfr NP PP \\
	NP \pfr ART ADJA NN & PP \pfr PRP NP \\
	ADJA \pfr ADJA ADJA & NP \pfr PN \\
	NP \pfr PRO NN & NP \pfr PRO ADJA NN
\end{tabular}

\subsection*{(b)}
\begin{tabular}{lll}
	S \pfr NP VP & VP \pfr VT NP & VP \pfr VI \\
	NP \pfr ART NN & NP \pfr PN & NP \pfr NP PP \\
	PP \pfr PRP NP & VP \pfr VP PP & NP \pfr ART ADJA NN \\
	ADJA \pfr ADJA ADJA & NP \pfr PRO NN & NP \pfr PRO ADJA NN
\end{tabular}

\begin{enumerate}
	\item Peter fuhr mit seinem roten Auto auf den großen neuen Parkplatz.
	\item Er mag seine Uhr.
	\item Das größte Konzert von Hans war in dem schönen heißen Sommer vor der größten Kirche in der Stadt.
\end{enumerate}

\noindent \textbf{Hinweis:} Alle Bäume wurden von mir nicht bis ins kleinste Detail ausgeführt. Um zu zeigen, dass das Prinzip (hoffentlich) klar ist, wird ein kleiner,
überschaubarer Baum in Aufgabe 7.1 (c) in voller Schönheit dargestellt.
\begin{enumerate}
	\item
		{\footnotesize \Tree [.S Peter [.VP [.VP fuhr [.PP mit [.NP seinem {roten Auto} ] ] ] [.PP auf \qroof{dem großen neuen Parkplatz}.NP ] ] ]}
	\item
		{\footnotesize \Tree [.S Er [.VP mag [.NP seine Uhr ] ] ]}
	\item
		{\tiny\Tree [.S [.NP \qroof{Das größte Konzert}.NP [.PP von Hans ] ] [.VP [.VP [.VP war [.PP in \qroof{dem schönen heißen Sommer}.NP ] ] [.PP vor \qroof{der größten Kirche}.NP ] ] [.PP in [.NP der Stadt ] ] ] ]}
\end{enumerate}

\subsection*{(c)}
Mit der Grammatik gibt es Probleme. \\
Die Grammatik kann z.B. keine Sätze der Form
\begin{center}
	\textit{Auch ohne Payback-Karte können Sie beim Einkauf sparen.}
\end{center}
erzeugen (zumindest habe ich keine passende Ableitung gefunden), obwohl diese grammatikalisch korrekt wären. \\
Ein mögliches Beispiel für einen Satz, der kein grammatischer Satz des Deutschen ist, aber von der Grammatik erzeugt wird, ist der folgende:
\begin{center}
	\textit{Hans mit Peter läuft ohne Otto.}
\end{center}
Erzeugt wurde der Satz wie folgt: \\
{\footnotesize \Tree [.S [.NP [.NP [.PN Hans ] ] [.PP [.PRP mit ] [.NP [.PN Peter ] ] ] ] [.VP [.VP [.VI läuft ] ] [.PP [.PRP ohne ] [.NP [.PN Otto ] ] ] ] ]}

\section*{Aufgabe 7.2}
Umschreibungen:
\begin{enumerate}
	\item Peter telefonierte mit seinem Handy von München aus und benachrichtigte den Kollegen.
	\item Peter benachrichtigte von München aus den Kollegen, der ein Handy besitzt.
	\item Peter benachrichtigte den Kollegen, der ein Handy besitzt und aus München stammt.
	\item Peter telefonierte mit seinem Handy, welches aus München kommt (welches in München produziert wurde), und benachrichtigte den Kollegen.
	\item Peter benachrichtige den Kollegen, der ein Handy besitzt, welches aus München kommt (welches in München produziert wurde).
\end{enumerate}
Strukturbäume:
\begin{enumerate}
	\item
		{\footnotesize \Tree [.S Peter [.PP [.PP [.VP benachrichtigte {den Kollegen} ] {mit dem Handy} ] {aus München} ] ]}
	\item
		{\footnotesize \Tree [.S Peter [.VP [.VP benachrichtigte [.NP {den Kollegen} {mit dem Handy} ] ] {aus München} ] ]}
	\item
		{\footnotesize \Tree [.S Peter [.VP benachrichtigte [.NP [.NP {den Kollegen} {mit dem Handy} ] {aus München} ] ] ]}
	\item
		{\footnotesize \Tree [.S Peter [.VP [.VP benachrichtigte {den Kollegen} ] [.PP mit [.NP {dem Handy} {aus München} ] ] ] ]}
	\item
		{\footnotesize \Tree [.S Peter [.VP benachrichtigte [.NP {den Kollegen} [.PP mit [.NP {dem Handy} {aus München} ] ] ] ] ]}
\end{enumerate}

\section*{Aufgabe 7.3}
\subsection*{(a)}
S $\rightarrow$ A S A \\
S $\rightarrow$ B S B \\
S $\rightarrow$ c \\
A $\rightarrow$ a \\
B $\rightarrow$ b

\subsection*{(b)}
Angenommen, die Sprache $L = \{wcw^R | w,w^R \in \{a,b\}^*\}$ wird von einem endlichen Automaten akzeptiert. Nach dem Pumping Lemma gibt es dann eine Zahl $k$, sodass
für jedes Wort $x$ mit $|x| \geqslant k$ eine Zerlegung $u_pv^i_pw_p$ mit $i \geqslant 0$ möglich ist, sodass $u_pv^i_pw_p \in L$. \\
Betrachten wir das Wort $wcw^R$ mit $|w|=|w^R|=k$, sodass das Wort die Gesamtlänge $2k+1 \geqslant k$ hat. \\
Es gibt 3 Fälle:
\begin{itemize}
	\item $v_p$ liegt in dem $w$-Teil (also im linken Teil): \\
		die Länge des Wortes links ist länger als rechts von dem $c$, \\
		d.h. $|w|=k+|v| \neq |w^R|$. $\Rightarrow$ Wort nicht in $L$.
	\item $v_p$ liegt in dem $w^R$-Teil (also im rechten Teil): \\
		die Länge des Wortes rechts ist länger als links von dem $c$, \\
		d.h. $|w^R|=k+|v| \neq |w|$. $\Rightarrow$ Wort nicht in $L$.
	\item $v_p$ geht über die Wortmitte hinaus: \\
		dies ist nicht möglich, da die Wortmitte nicht mehr durch $c$ gekennzeichnet wäre. $\Rightarrow$ Wort nicht in $L$.
\end{itemize}

\subsection*{(c)}
\begin{picture}(111,44)(0,-44)
\node[NLangle=0.0,ilength=8.0,Nmarks=i](n0)(35.46,-20.75){1}

\node[NLangle=0.0,Nmarks=r](n1)(71.88,-20.75){2}

\drawedge(n0,n1){$\left<c,\varepsilon,\varepsilon\right>$}

\drawloop[loopangle=-90.0](n1){$\left<b,b,\varepsilon\right>$}

\drawloop[loopangle=-90.0](n0){$\left<b,\varepsilon,b\right>$}

\drawloop(n0){$\left<a, \varepsilon, a\right>$}

\drawloop(n1){$\left<a,a,\varepsilon\right>$}
\end{picture}

\end{document}
