Mercurial > 13ss.theoinf

comparison notes/tex/ue01_notes.tex @ 2:95b88347f465

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ue01 notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Tue, 23 Apr 2013 00:08:00 +0200
parents
children 73037b3dde60
comparison
equal deleted inserted replaced
1:594b9dd142e7 2:95b88347f465
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 \usepackage{tabu}
20
21 \usepackage{beamerthemeLEA2}
22
23 \newcommand{\N} {\mathbb{N}} % natürliche Zahlen
24 \newcommand{\Z} {\mathbb{Z}} % ganze Zahlen
25 \newcommand{\R} {\mathbb{R}} % reelle Zahlen
26 \newcommand{\Prob} {\mathrm{P}} % Wahrscheinlichkeit
27 \newcommand{\inter} {\cap} % Schnittmenge
28 \newcommand{\union} {\cup} % Vereinigung
29 \newcommand{\Oh} {\mathcal{O}} % O-Notation (Landau-Symbole)
30 \newcommand{\mycite}[1]{\textcolor{tumgreen}{[#1]}}
31
32 \tikzstyle{every edge} = [draw,very thick,->,>=latex]
33 \tikzstyle{every state} = [circle,thick,draw,fill=tumblue!10]
34
35 \title{Übung 1}
36 \subtitle{Theoretische Informatik Sommersemester 2013}
37 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
38
39 \begin{document}
40
41 \begin{frame}
42 \titlepage
43 \end{frame}
44
45 \begin{frame}
46 \frametitle{Was ist Theoinf?}
47
48 Aus der VL
49 \vspace{1em}
50
51 \begin{itemize}
52 \item Automatentheorie
53 \begin{itemize}
54 \item Rechner mit endlichem oder kellerartigem Speicher
55 \end{itemize}
56 \vspace{0.5em}
57 \item Grammatiken
58 \begin{itemize}
59 \item Syntax von Programmiersprachen
60 \end{itemize}
61 \vspace{0.5em}
62 \item Berechenbarkeitstheorie
63 \begin{itemize}
64 \item Untersuchung der Grenzen, was Rechner prinzipiell können
65 \end{itemize}
66 \vspace{0.5em}
67 \item Komplexitätstheorie
68 \begin{itemize}
69 \item Untersuchung der Grenzen, was Rechner mit begrenzten Ressourcen können
70 \end{itemize}
71 \end{itemize}
72 \end{frame}
73
74 \begin{frame}
75 \frametitle{Grundlegendes}
76
77 \begin{definition}
78 \begin{itemize}
79 \item Ein \alert{Alphabet} $\Sigma$ ist eine endliche Menge.
80 \item Ein \alert{Wort} über $\Sigma$ ist eine endliche Folge von Zeichen.
81 \item Eine Teilmenge $L \subseteq \Sigma^*$ ist eine \alert{formale Sprache}
82 \end{itemize}
83 \end{definition}
84
85 \vfill
86
87 \begin{definition}[Operationen auf Sprachen]
88 \begin{itemize}
89 \item $\alert{AB} = \left\{ uv \mid u \in A \wedge v \in B \right\}$
90 \item $\alert{A^n} = \left\{w_1 \ldots w_n \mid w_1 \ldots w_n \in A \right\}$,\qquad $A^0 = \{\epsilon\}$
91 \item $\alert{A^*} = \bigcup_{n \in \N_0} A^n$
92 \end{itemize}
93 \end{definition}
94 \end{frame}
95
96 \begin{frame}
97 \frametitle{DFA}
98
99 \begin{definition}[Deterministischer endlicher Automat]
100 Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem
101 \begin{itemize}
102 \item endlichen Menge von \alert{Zuständen} $Q$
103 \item endlichen \alert{Eingabealphabet} $\Sigma$
104 \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto Q$
105 \item \alert{Startzustand} $q_0 \in Q$
106 \item Menge von \alert{Endzuständen} $F \subseteq Q$
107 \end{itemize}
108 \end{definition}
109
110 \vfill
111 \pause
112
113 \begin{center}
114 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
115 \node[state, initial] (q0) {$q_0$};
116 \node[state, accepting] (q1) [right of = q0] {$q_1$};
117 \node[state] (q2) [right of = q1] {$q_2$};
118
119 \draw[->] (q0) edge [loop above] node {0} (q0);
120 \draw[->] (q2) edge [loop above] node {1} (q2);
121 \draw[->] (q0) edge [bend left] node {1} (q1);
122 \draw[->] (q1) edge [bend left] node {1} (q0);
123 \draw[->] (q1) edge [bend left] node {0} (q2);
124 \draw[->] (q2) edge [bend left] node {0} (q1);
125 \end{tikzpicture}
126 \end{center}
127 \end{frame}
128
129 \begin{frame}
130 \frametitle{NFA}
131 \begin{definition}[Nicht-Deterministischer endlicher Automat]
132 Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
133 \begin{itemize}
134 \item $Q, \Sigma, q_0, F$ wie ein DFA
135 \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto P(Q)$
136 \end{itemize}
137 \end{definition}
138
139 \vfill
140 \pause
141
142 \begin{center}
143 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
144 \node[state, initial] (q0) {$q_0$};
145 \node[state, accepting] (q1) [right of = q0] {$q_1$};
146
147 \draw[->] (q0) edge [loop above] node {0,1} (q0);
148 \draw[->] (q0) edge node {1} (q1);
149 \end{tikzpicture}
150 \end{center}
151 \end{frame}
152
153 \begin{frame}
154 \frametitle{$\epsilon$-NFA}
155 \begin{definition}[NFA mit $\epsilon$-Übergängen]
156 Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit
157 \begin{itemize}
158 \item $Q, \Sigma, q_0, F$ wie ein DFA
159 \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \mapsto P(Q)$
160 \end{itemize}
161 \end{definition}
162
163 \vfill
164 \pause
165
166 \begin{center}
167 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=]
168 \node[state] (q1) {$q_1$};
169 \node[state, initial] (q0) [left of = q1] {$q_0$};
170 \node[state, accepting] (q2) [right of = q1] {$q_2$};
171
172 \draw[->] (q0) edge [red] node {$\epsilon$} (q1);
173 \draw[->] (q1) edge [loop above] node {0,1} (q1);
174 \draw[->] (q1) edge node {1} (q2);
175 \draw[->] (q0) edge [bend right, red] node {$\epsilon$} (q2);
176 \end{tikzpicture}
177 \end{center}
178 \end{frame}
179
180 \begin{frame}
181 \frametitle{Automaten}
182 \begin{block}{Übergangsfunktionen}
183 Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen.
184
185 \begin{description}
186 \item[DFA] $\delta : Q \times \Sigma \mapsto Q$
187 \item[NFA] $\delta : Q \times \Sigma \mapsto \alert{P(Q)}$
188 \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \mapsto \alert{P(Q)}$
189 \end{description}
190 \end{block}
191
192 \vfill
193
194 \begin{theorem}
195 \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln.
196 \end{theorem}
197 \end{frame}
198
199 \begin{frame}
200 \frametitle{Tutoraufgabe 3}
201
202 \begin{center}
203 \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=]
204 \node[state, initial] (q0) {$q_0$};
205 \node[state, accepting] (q1) [above right of = q0] {$q_1$};
206 \node[state] (q2) [right of = q1] {$q_2$};
207 \node[state] (q3) [below right of = q0] {$q_3$};
208 \node[state] (q4) [right of = q3] {$q_4$};
209
210 \draw[->] (q0) edge node {0} (q1);
211 \draw[->] (q0) edge node {1} (q3);
212
213 \draw[->] (q1) edge [loop above] node {0} (q1);
214 \draw[->] (q2) edge [loop right] node {1} (q2);
215 \draw[->] (q4) edge [loop right] node {0} (q4);
216
217 \draw[->] (q1) edge [bend left] node {1} (q2);
218 \draw[->] (q2) edge [bend left] node {0} (q1);
219 \draw[->] (q3) edge [bend left] node {0,1} (q4);
220 \draw[->] (q4) edge [bend left] node {1} (q3);
221 \end{tikzpicture}
222 \end{center}
223 \end{frame}
224 \end{document}