Mercurial > 13ss.theoinf

comparison notes/tex/ue06_notes.tex @ 25:6a76770d5cfb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ue06 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 04 Jun 2013 00:23:37 +0200
parents
children 914314a7117d
comparison
equal deleted inserted replaced
24:410237e0bad0 25:6a76770d5cfb
1 \documentclass[compress, german, t]{beamer}
2
3 \usepackage[ngerman,english]{babel}
4 \uselanguage{German}
5 \languagepath{German}
6
7 \usepackage[T1]{fontenc}
8 \usepackage[utf8]{inputenc}
9
10 \usepackage{helvet}
11 \usepackage{url}
12 \usepackage{listings}
13 \usepackage{xcolor}
14 \usepackage{tikz}
15 \usepackage{pgfplots}
16 \usetikzlibrary{automata}
17 \usetikzlibrary{calc}
18 \usetikzlibrary{shapes.geometric}
19 \usetikzlibrary{positioning}
20 \usepackage{tabu}
21
22 \usepackage{beamerthemeLEA2}
23
24 \newcommand{\N} {\mathbb{N}} % natürliche Zahlen
25 \newcommand{\Z} {\mathbb{Z}} % ganze Zahlen
26 \newcommand{\R} {\mathbb{R}} % reelle Zahlen
27 \newcommand{\Prob} {\mathrm{P}} % Wahrscheinlichkeit
28 \newcommand{\Oh} {\mathcal{O}} % O-Notation (Landau-Symbole)
29 \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}}
30
31 \tikzstyle{every edge} = [draw,very thick,->,>=latex]
32 \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10]
33 \tikzstyle{automaton} = [shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
34 \tikzstyle{small} = [every node/.style={scale=0.5}, baseline=(current bounding box.north), font=\LARGE]
35
36 \title{Übung 5: CNF und CFL-Pumping Lemma}
37 \subtitle{Theoretische Informatik Sommersemester 2013}
38 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
39
40 \begin{document}
41
42 \begin{frame}
43 \titlepage
44 \end{frame}
45
46 \begin{frame}
47 \frametitle{CNF}
48 \setbeamercovered{dynamic}
49
50 \begin{definition}[Chomsky-Normalform]
51 Eine kontextfreie Grammatik ist in \alert{Chomsky-Normalform} (CNF) genau dann wenn alle Produktionen die Form
52 \[
53 A \rightarrow \alert{a} \quad \text{oder} \quad A \rightarrow \alert{BC}
54 \]
55 haben.
56 \end{definition}
57
58 \vfill
59
60 \begin{theorem}
61 Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit
62 \[
63 L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}}
64 \]
65 \end{theorem}
66 \end{frame}
67
68 \begin{frame}
69 \frametitle{CNF Konstruktion}
70 \setbeamercovered{dynamic}
71
72 \begin{block}{Idee}
73 Sei $G = (V, \Sigma, P, S)$ eine CFG.
74 \begin{enumerate}
75 \item<1,2-> Eliminiere \alert{$\epsilon$-Produktionen}
76 \item<1,3-> Eliminiere \alert{Kettenproduktionen}
77 \item<1,4-> \alert{Ersetze Terminale} durch Nichtterminale
78 \item<1,5-> \alert{Verkürze Ketten} von Nichtterminalen der Länge $\geq 3$
79 \end{enumerate}
80 \end{block}
81
82 \vspace{1em}
83
84 \only<2> {
85 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.
86 \begin{align*}
87 S &\rightarrow Ab, \quad A \rightarrow aAA \mid \epsilon \\
88 \intertext{neu:}
89 S &\rightarrow \alert{b} \\
90 A &\rightarrow \alert{aA \mid a}
91 \end{align*}
92 }
93
94 \only<3> {
95 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.
96 \begin{align*}
97 S &\rightarrow A, \quad A \rightarrow a \mid B, \quad B \rightarrow bS \\
98 \intertext{neu:}
99 A &\rightarrow \alert{a \mid bS} \\
100 S &\rightarrow \alert{a \mid bS}
101 \end{align*}
102 }
103
104 \only<4> {
105 Ersetze jedes \alert{$a \in \Sigma$} in einer rechten Seite \alert{länger als $1$} durch ein neues Nichtterminal.
106 \begin{align*}
107 S &\rightarrow aa \mid Bb \mid b, \quad B \rightarrow \ldots \\
108 \intertext{neu:}
109 S &\rightarrow \alert{X_aX_a \mid BX_b \mid b} \\
110 X_a &\rightarrow \alert{a}, \quad X_b \rightarrow \alert{b}
111 \end{align*}
112 }
113
114 \only<5> {
115 Ersetze jede Produktion der Form $A \rightarrow B_1B_2\ldots B_k$ durch neue Nichtterminale mit Produktionen der Länge $2$.
116 \begin{align*}
117 S &\rightarrow X_aX_bBX_a, \quad X_a \rightarrow a, \quad X_b \rightarrow b, \quad B \rightarrow \ldots \\
118 \intertext{neu:}
119 S &\rightarrow \alert{X_aT_1} \\
120 T_1 &\rightarrow \alert{X_bT_2}, \quad T_2 \rightarrow \alert{BX_a} \\
121 \end{align*}
122 }
123 \end{frame}
124
125 \begin{frame}
126 \frametitle{Eigenschaften von Symbolen}
127 \setbeamercovered{dynamic}
128
129 \begin{definition}
130 Sei $G = (V, \Sigma, P, S)$ eine CFG. \\
131 Ein Symbol $X \in V \cup \Sigma$ ist
132 \begin{description}
133 \item[nützlich] es gibt $S \rightarrow_G^* w \in \Sigma^*$ in der X \alert{vorkommt}
134 \item[erzeugend] es gibt $\alert{X} \rightarrow_G^* w \in \Sigma^*$
135 \item[erreichbar] es gibt $S \rightarrow_G^* \alpha \alert{X} \beta$
136 \end{description}
137 \end{definition}
138
139 \vfill
140
141 \begin{theorem}
142 Nützliche Symbole \alert{sind} erzeugend und erreichbar. Aber \alert{nicht} notwendigerweise umgekehrt.
143 \[
144 S \rightarrow AB \mid a, \quad A \rightarrow b
145 \]
146 \end{theorem}
147 \end{frame}
148
149 \begin{frame}
150 \frametitle{Pumping Lemma für CFLs}
151 \setbeamercovered{dynamic}
152
153 \begin{theorem}[Pumping Lemma für kontextfreie Sprachen]
154 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
155 \begin{itemize}
156 \item $vx \alert{\neq \epsilon}$
157 \item $|vwx| \alert{\leq n}$
158 \item $\forall i \alert{\geq 0}. uv^iwx^iy \in L$
159 \end{itemize}
160 \end{theorem}
161
162 \vfill
163
164 \begin{center}
165 \begin{columns}
166 \begin{column}{.4\textwidth}
167 \begin{tikzpicture}
168 \coordinate (outer) at (2, 2.4);
169 \coordinate (middle) at (2.2, 1.2);
170 \coordinate (inner) at (2.2, 0.6);
171 % outer
172 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
173 % middle
174 \draw[fill=tumgreen!40] (1.2, 0) -- (1.7, 0) -- (inner) -- (2.7, 0) -- (3.2, 0) -- (middle) -- (1.2, 0);
175 % inner
176 \draw[fill=tumblue!40] (1.7, 0) -- (inner) -- (2.7, 0) -- (1.7, 0);
177
178 % path
179 \draw[dashed, thick] (outer) -- (middle) -- (inner);
180 \draw[fill] (outer) circle (1pt);
181 \draw[fill] (middle) circle (1pt);
182 \draw[fill] (inner) circle (1pt);
183
184 % nodes
185 \node[below] at (0.6, 0) {$u$};
186 \node[below] at (1.45, 0) {$v$};
187 \node[below] at (2.2, 0) {$w$};
188 \node[below] at (2.95, 0) {$x$};
189 \node[below] at (3.6, 0) {$y$};
190 \end{tikzpicture}
191 \end{column}
192 \begin{column}{.4\textwidth}
193 \begin{tikzpicture}
194 \coordinate (outer) at (2, 2.4);
195 \coordinate (middle) at (2.2, 1.2);
196 \coordinate (inner) at (2.2, 0.6);
197 % outer
198 \draw[fill=tumred!40] (0, 0) -- (1.2, 0) -- (middle) -- (3.2, 0) -- (4, 0) -- (outer) node[above] {$S$} -- (0, 0);
199 % inner
200 \draw[fill=tumblue!40] (1.7, 0.6) -- (middle) -- (2.7, 0.6) -- (1.7, 0.6);
201
202 % path
203 \draw[dashed, thick] (outer) -- (middle);
204 \draw[fill] (outer) circle (1pt);
205 \draw[fill] (middle) circle (1pt);
206
207 % nodes
208 \node[below] at (0.6, 0) {$u$};
209 \node[below] at (2.2, 0) {$w$};
210 \node[below] at (3.6, 0) {$y$};
211 \end{tikzpicture}
212 \end{column}
213 \end{columns}
214 \end{center}
215 \end{frame}
216
217 \end{document}