|
25
|
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} |
