changeset 25:6a76770d5cfb

ue06 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 04 Jun 2013 00:23:37 +0200
parents 410237e0bad0
children 914314a7117d
files notes/tex/ue06_notes.tex notes/ue06_notes.pdf
diffstat 2 files changed, 217 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/notes/tex/ue06_notes.tex	Tue Jun 04 00:23:37 2013 +0200
@@ -0,0 +1,217 @@
+\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: CNF und CFL-Pumping Lemma}
+\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{CNF}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}[Chomsky-Normalform]
+        Eine kontextfreie Grammatik ist in \alert{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form
+        \[
+            A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC}
+        \]
+        haben.
+    \end{definition}
+
+    \vfill
+
+    \begin{theorem}
+        Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit 
+        \[
+            L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}}
+        \]
+    \end{theorem}
+\end{frame}
+
+\begin{frame}
+    \frametitle{CNF Konstruktion}
+    \setbeamercovered{dynamic}
+
+    \begin{block}{Idee}
+        Sei $G = (V, \Sigma, P, S)$ eine CFG.
+        \begin{enumerate}
+            \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen}
+            \item<1,3-> Eliminiere \alert{Kettenproduktionen}
+            \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale
+            \item<1,5-> \alert{Verkürze Ketten} von Nichtterminalen der Länge $\geq 3$
+        \end{enumerate}
+    \end{block}
+
+    \vspace{1em}
+
+    \only<2> {
+        Sind \alert{$B \rightarrow \epsilon$} und \alert{$A \rightarrow \alpha B \beta$} in $P$, dann füge \alert{$A \rightarrow \alpha \beta$} hinzu. Entferne danach alle $\epsilon$-Produktionen.
+        \begin{align*}
+            S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\
+            \intertext{neu:}
+            S &\rightarrow \alert{b} \\
+            A &\rightarrow \alert{aA \mid a}
+        \end{align*}
+    }
+
+    \only<3> {
+        Sind \alert{$A \rightarrow B$} und \alert{$B \rightarrow \alpha$} in $P$, dann füge \alert{$A \rightarrow \alpha$} hinzu. Entferne danach alle Kettenproduktionen und unerreichbaren Symbole.
+        \begin{align*}
+            S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\
+            \intertext{neu:}
+            A &\rightarrow \alert{a \mid bS} \\
+            S &\rightarrow \alert{a \mid bS}
+        \end{align*}
+    }
+
+    \only<4> {
+        Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal.
+        \begin{align*}
+            S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\
+            \intertext{neu:}
+            S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\
+            X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b}
+        \end{align*}
+    }
+
+    \only<5> {
+        Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$.
+        \begin{align*}
+            S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\
+            \intertext{neu:}
+            S &\rightarrow \alert{X_aT_1} \\
+            T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\
+        \end{align*}
+    }
+\end{frame}
+
+\begin{frame}
+    \frametitle{Eigenschaften von Symbolen}
+    \setbeamercovered{dynamic}
+
+    \begin{definition}
+        Sei $G = (V, \Sigma, P, S)$ eine CFG. \\
+        Ein Symbol $X \in V \cup \Sigma$ ist
+        \begin{description}
+            \item[nützlich] es gibt $S \rightarrow_G^* w \in \Sigma^*$ in der X \alert{vorkommt}
+            \item[erzeugend] es gibt $\alert{X} \rightarrow_G^* w \in \Sigma^*$
+            \item[erreichbar] es gibt $S \rightarrow_G^* \alpha \alert{X} \beta$
+        \end{description}
+    \end{definition}
+
+    \vfill
+
+    \begin{theorem}
+        Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt.
+        \[
+            S \rightarrow AB \mid a, \quad A \rightarrow b
+        \]
+    \end{theorem}
+\end{frame}
+
+\begin{frame}
+    \frametitle{Pumping Lemma für CFLs}
+    \setbeamercovered{dynamic}
+
+    \begin{theorem}[Pumping Lemma für kontextfreie Sprachen]
+        Sei $L \subseteq \Sigma^*$ kontextfrei. Dann gibt es ein $n > 0$, so dass sich \alert{jedes} $z \in L$ mit $|z| \geq n$ so in \alert{$z = uvwxy$} zerlegen lässt, dass
+        \begin{itemize}
+            \item $vx \alert{\neq \epsilon}$
+            \item $|vwx| \alert{\leq n}$
+            \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$
+        \end{itemize}
+    \end{theorem}
+
+    \vfill
+
+    \begin{center}
+        \begin{columns}
+            \begin{column}{.4\textwidth}
+                \begin{tikzpicture}
+                    \coordinate (outer) at (2, 2.4);
+                    \coordinate (middle) at (2.2, 1.2);
+                    \coordinate (inner) at (2.2, 0.6);
+                    % outer
+                    \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
+                    % middle
+                    \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0);
+                    % inner
+                    \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0);
+
+                    % path
+                    \draw[dashed, thick] (outer) -- (middle) -- (inner);
+                    \draw[fill] (outer) circle (1pt);
+                    \draw[fill] (middle) circle (1pt);
+                    \draw[fill] (inner) circle (1pt);
+
+                    % nodes
+                    \node[below] at (0.6, 0) {$u$};
+                    \node[below] at (1.45, 0) {$v$};
+                    \node[below] at (2.2, 0) {$w$};
+                    \node[below] at (2.95, 0) {$x$};
+                    \node[below] at (3.6, 0) {$y$};
+                \end{tikzpicture}
+            \end{column}
+            \begin{column}{.4\textwidth}
+                \begin{tikzpicture}
+                    \coordinate (outer) at (2, 2.4);
+                    \coordinate (middle) at (2.2, 1.2);
+                    \coordinate (inner) at (2.2, 0.6);
+                    % outer
+                    \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
+                    % inner
+                    \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6);
+
+                    % path
+                    \draw[dashed, thick] (outer) -- (middle);
+                    \draw[fill] (outer) circle (1pt);
+                    \draw[fill] (middle) circle (1pt);
+
+                    % nodes
+                    \node[below] at (0.6, 0) {$u$};
+                    \node[below] at (2.2, 0) {$w$};
+                    \node[below] at (3.6, 0) {$y$};
+                \end{tikzpicture}
+            \end{column}
+        \end{columns}
+    \end{center}
+\end{frame}
+
+\end{document}
Binary file notes/ue06_notes.pdf has changed