\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{bis zum 27. April 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Semantik von Programmiersprachen}\hfill SoSe 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Max Willert

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Strukturelle Induktion \"uber Boolesche Terme}{10 Punkte}

Sei $V = \{x_1, x_2, \dots\}$ eine Menge von 
Variablen. Ein \emph{Boolescher Term} ist folgenderma\ss{}en
definiert:
\begin{itemize}
	\item F\"ur alle $x \in V$ ist $x$ ein Boolescher Term.
	\item Wenn $t$ ein Boolescher Term ist, so ist auch $(\neg t)$ ein Boolescher Term.
	\item Wenn $t_1$ und $t_2$ Boolesche Terme sind, so sind auch $(t_1 \wedge t_2)$ und
	      $(t_1 \vee t_2)$ Boolesche Terme.
	\item Ansonsten gibt es keine Booleschen Terme.
\end{itemize}
Die \emph{Semantik} eines Booleschen Terms $t$, in dem $n$ Variablen vorkommen,
ist die $n$-stellige Boolesche Funktion $f_t: \{0,1\}^n \rightarrow \{0,1\}$, die durch
$t$ dargestellt wird. Zwei Boolesche Terme $t_1$ und $t_2$ hei\ss{}en \emph{\"aquivalent}, falls 
in ihnen die gleichen Variablen vorkommen und falls $f_{t_1} = f_{t_2}$ ist.

Beweisen Sie detailliert duch strukturelle Induktion: Zu jedem Booleschen Term
$t$ existiert ein \"aquivalenter Boolescher Term, in dem die Negationen ausschlie\ss{}lich 
direkt vor den Variablen vorkommen. Sie d\"urfen f\"ur Ihren Beweis bekannte Tatsachen
aus der Aussagenlogik verwenden.

\AUFGABE{Regul\"are Ausdr\"ucke} {10 Punkte}

Sei $\Sigma = \{0, 1\}$. Ein \emph{regul\"arer Ausdruck}
\"uber $\Sigma$ ist folgenderma\ss{}en definiert:

\begin{itemize}
        \item $\emptyset$ und $\varepsilon$ sind regul\"are Ausdr\"ucke.
	\item F\"ur alle $\sigma \in \Sigma$ ist $\sigma$ ein regul\"arer Ausdruck.
	\item Wenn $r$ ein regul\"arer Ausdruck ist, so ist auch $(r^*)$ ein regul\"arer Ausdruck.
	\item Wenn $r_1$ und $r_2$ regul\"are Ausdr\"ucke sind, so sind auch 
		$(r_1 \circ r_2)$ und
	      $(r_1 \cup r_2)$ regul\"are Ausdr\"ucke
	\item Ansonsten gibt es keine regul\"aren Ausdr\"ucke.
\end{itemize}

Die \emph{Semantik} eines regul\"aren Ausdrucks $r$ ist die Sprache $L(r) \subseteq \Sigma^*$,
welche folgenderma\ss{}en definiert ist:
\begin{itemize}
	\item $L(\emptyset) = \emptyset$, $L(\varepsilon) = \{\varepsilon\}$,                   
      $L(\sigma) = \{\sigma\}$, f\"ur alle $\sigma \in \Sigma$.
	\item $L((r^*)) = L(r)^*$, $L((r_1 \circ r_2)) = L(r_1) \circ L(r_2)$ und
		$L((r_1 \cup r_2)) = L(r_1) \cup L(r_2)$.
\end{itemize}
\newpage
Beweisen Sie:

\begin{enumerate}
  \item F\"ur alle regul\"aren Ausdr\"ucke $r_1, r_2$ gilt:
	 $L((r_1 \cup r_2)) = L((r_2 \cup r_1))$.
  \item F\"ur alle regul\"aren Ausdr\"ucke $r$ gilt:
	  $L((r \circ \emptyset)) = \emptyset$.
  \item F\"ur alle regul\"aren Ausdr\"ucke $r$ gilt:
	  $L((\varepsilon \circ r)) = L(r)$.
  \item F\"ur alle regul\"aren Ausdr\"ucke $r_1, r_2, r_3$ gilt:
	  $L((r_1 \circ (r_2 \cup r_3))) = L((r_1 \circ r_2)) \cup L((r_1 \circ r_3))$.
  \item  F\"ur alle regul\"aren Ausdr\"ucke $r_1, r_2$ gilt:
	  $L(r_1) \subseteq L((r_1 \cup (r_2)^*))$.
\end{enumerate}

\AUFGABE {Arithmetische Ausdr\"ucke}{10 Punkte}

Betrachten Sie die folgende kontextfreie Grammatik f\"ur
arithmetische Ausdr\"ucke:
\begin{verbatim}
  Z -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
  E -> Z | E + E | E - E | E * E | (E)
\end{verbatim}

\begin{enumerate}
  \item Geben Sie zwei verschiedene Syntaxb\"aume f\"ur
	  den arithmetischen Ausdruck \texttt{2+5*6-2-4} an.
  \item Geben Sie eine eindeutige Grammatik f\"ur arithmetische
	  Ausdr\"ucke an. Begr\"unden Sie kurz, warum Ihre
	  Grammatik eindeutig ist (es ist kein formaler Beweis n\"otig).
  \item Definieren Sie formal eine Semantik f\"ur Ihre Grammatik aus
	  (b), d.h., beschreiben Sie eine Funktion $f$, die jedem
	  g\"ultigen arithmetischen Ausdruck sinnvoll eine nat\"urliche Zahl zuordnet.
  \item Bestimmen Sie mit Hilfe Ihrer Definiton aus (c) die Semantik des
	    arithmetischen Ausdrucks \texttt{2+5*6-2-4}.
\end{enumerate}
\end{description}
\end{document}
