# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1369692180 -7200
# Node ID 56490ea79fb2cca2695e0c3a445f061e1272eaa0
# Parent  95ca58a842579c0bb640f3aadfc2d7cd4b7cddea
ue05 notes

diff -r 95ca58a84257 -r 56490ea79fb2 notes/tex/ue05_notes.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue05_notes.tex	Tue May 28 00:03:00 2013 +0200
@@ -0,0 +1,132 @@
+\documentclass[compress, german, t]{beamer}
+
+\usepackage[ngerman,english]{babel}
+\uselanguage{German}
+\languagepath{German}
+
+\usepackage[T1]{fontenc}
+\usepackage[utf8]{inputenc}
+
+\usepackage{helvet}
+\usepackage{url}
+\usepackage{listings}
+\usepackage{xcolor}
+\usepackage{tikz}
+\usepackage{pgfplots}
+\usetikzlibrary{automata}
+\usetikzlibrary{calc}
+\usetikzlibrary{shapes.geometric}
+\usetikzlibrary{positioning}
+\usepackage{tabu}
+
+\usepackage{beamerthemeLEA2}
+
+\newcommand{\N}       {\mathbb{N}}          % natürliche Zahlen
+\newcommand{\Z}       {\mathbb{Z}}          % ganze Zahlen
+\newcommand{\R}       {\mathbb{R}}          % reelle Zahlen
+\newcommand{\Prob}    {\mathrm{P}}          % Wahrscheinlichkeit
+\newcommand{\Oh}      {\mathcal{O}}         % O-Notation (Landau-Symbole)
+\newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}}
+
+\tikzstyle{every edge} = [draw,very thick,->,>=latex]
+\tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10]
+\tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
+\tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE]
+
+\title{Übung 5: Kontextfreie Sprachen}
+\subtitle{Theoretische Informatik Sommersemester 2013}
+\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
+
+\begin{document}
+
+\begin{frame}
+    \titlepage
+\end{frame}
+
+\begin{frame}
+    \frametitle{Grammatiken}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Kontextfreie Grammatik]
+        Eine \alert{kontextfreie Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel:
+        \begin{description}
+            \item[V] endlich viele \alert{Nichtterminale} (Variablen)
+            \item[$\Sigma$] ein Alphabet von \alert{Terminalen}
+            \item[P] endlich viele \alert{Produktionen} $\subseteq V \times \left( V \cup \Sigma \right)^*$
+            \item[S] ein \alert{Startsymbol}
+        \end{description}
+    \end{definition}
+
+    \begin{example}[Vorbereitung 3]
+        $\Sigma = \left\{ 0, 1 \right\}$. Grammatik für alle Wörter ungerader Länge, bei denen alle Nullen vor der ersten Eins stehen und weniger Nullen als Einsen vorhanden sind.
+        \pause
+        \[
+            S \rightarrow 0S1 \mid S11 \mid 1
+        \]
+    \end{example}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Ableitungsrelation}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Ableitungsrelation]
+        Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$:
+        \[
+            \alpha \rightarrow_G \beta
+        \]
+        gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass
+        \[
+            \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2
+        \]
+    \end{definition}
+
+    \begin{example}[Vorbereitung 3]
+        Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
+        \begin{align*}
+            S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\
+            \Rightarrow S &\rightarrow_G^* 0011111
+        \end{align*}
+    \end{example}
+\end{frame}
+
+\begin{frame}[c]
+    \frametitle{Kontextfreie Sprache}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Kontextfreie Sprache]
+        Eine kontextfreie Grammatik $G = (V, \Sigma, P, S)$ \alert{erzeugt} die Sprache
+        \[
+            L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\}
+        \]
+        Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$.
+    \end{definition}
+
+\end{frame}
+
+\begin{frame}
+    \frametitle{Induktive Sprachdefinition}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Induktive Sprachdefinition}
+        Die \alert{induktive Definition} ($\Longrightarrow$) erzeugt Wörter \alert{bottom-up}, setzt also kleine Wörter zu größeren zusammen.
+    \end{block}
+
+    \begin{example}[Vorbereitung 3]
+        Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
+
+        \begin{align*}
+            1 &\in L_G(S) \\
+            u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\
+            u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S)
+        \end{align*}
+
+        Also z.B:
+
+        \[
+            1 \in L_G(S) \Longrightarrow 0\alert{1}0 \in L_G(S) \Longrightarrow \alert{010}11 \in L_G(S)
+        \]
+    \end{example}
+\end{frame}
+
+\end{document}
diff -r 95ca58a84257 -r 56490ea79fb2 notes/ue05_notes.pdf
Binary file notes/ue05_notes.pdf has changed