# HG changeset patch # User Markus Kaiser # Date 1370298217 -7200 # Node ID 6a76770d5cfb41263bc009a559ba5554ec5aec49 # Parent 410237e0bad058e0761de094d789bf32097975fe ue06 notes diff -r 410237e0bad0 -r 6a76770d5cfb notes/tex/ue06_notes.tex --- /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} diff -r 410237e0bad0 -r 6a76770d5cfb notes/ue06_notes.pdf Binary file notes/ue06_notes.pdf has changed