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