Mercurial > 13ss.theoinf
view notes/tex/ue01_notes.tex @ 7:95760b319e91
exact times; title
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Tue, 30 Apr 2013 01:31:39 +0200 |
parents | 73037b3dde60 |
children | 90ffda7e20c7 |
line wrap: on
line source
\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} \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] \title{Übung 1: Sprachen und Automaten} \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{Organisatorisches} \begin{itemize} \item Mail: \href{mailto:tutor@zfix.org}{tutor@zfix.org} \item Web: \href{tutor.zfix.org}{tutor.zfix.org} \vfill \item Wann? \begin{itemize} \item Dienstag 10:15-11:45 00.08.038 \item Dienstag 12:05-13:35 00.08.038 \end{itemize} \item Übungsablauf, Aufgabentypen \item Hausaufgaben \begin{itemize} \item Abgabe am Montag 14h, \alert{allein} \item Rückgabe in der \alert{richtigen} Übung \item Notenbonus für 40\% der Punkte, 40\% in der zweiten Hälfte \end{itemize} \item Klausur \begin{itemize} \item Endterm: Mi 31.07. 11.30-14h \item Wiederholung: Do 26.09. 11-13.30h \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Was ist Theoinf?} Aus der VL \vspace{1em} \begin{itemize} \item Automatentheorie \begin{itemize} \item Rechner mit endlichem oder kellerartigem Speicher \end{itemize} \vspace{0.5em} \item Grammatiken \begin{itemize} \item Syntax von Programmiersprachen \end{itemize} \vspace{0.5em} \item Berechenbarkeitstheorie \begin{itemize} \item Untersuchung der Grenzen, was Rechner prinzipiell können \end{itemize} \vspace{0.5em} \item Komplexitätstheorie \begin{itemize} \item Untersuchung der Grenzen, was Rechner mit begrenzten Ressourcen können \end{itemize} \end{itemize} \end{frame} \begin{frame} \frametitle{Grundlegendes} \begin{definition} \begin{itemize} \item Ein \alert{Alphabet} $\Sigma$ ist eine endliche Menge. \item Ein \alert{Wort} über $\Sigma$ ist eine endliche Folge von Zeichen. \item Eine Teilmenge $L \subseteq \Sigma^*$ ist eine \alert{formale Sprache} \end{itemize} \end{definition} \vfill \begin{definition}[Operationen auf Sprachen] \begin{itemize} \item $\alert{AB} = \left\{ uv \mid u \in A \wedge v \in B \right\}$ \item $\alert{A^n} = \left\{w_1 \ldots w_n \mid w_1 \ldots w_n \in A \right\}$,\qquad $A^0 = \{\epsilon\}$ \item $\alert{A^*} = \bigcup_{n \in \N_0} A^n$ \end{itemize} \end{definition} \end{frame} \begin{frame} \frametitle{DFA} \begin{definition}[Deterministischer endlicher Automat] Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem \begin{itemize} \item endlichen Menge von \alert{Zuständen} $Q$ \item endlichen \alert{Eingabealphabet} $\Sigma$ \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto Q$ \item \alert{Startzustand} $q_0 \in Q$ \item Menge von \alert{Endzuständen} $F \subseteq Q$ \end{itemize} \end{definition} \vfill \pause \begin{center} \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] \node[state, initial] (q0) {$q_0$}; \node[state, accepting] (q1) [right of = q0] {$q_1$}; \node[state] (q2) [right of = q1] {$q_2$}; \draw[->] (q0) edge [loop above] node {0} (q0); \draw[->] (q2) edge [loop above] node {1} (q2); \draw[->] (q0) edge [bend left] node {1} (q1); \draw[->] (q1) edge [bend left] node {1} (q0); \draw[->] (q1) edge [bend left] node {0} (q2); \draw[->] (q2) edge [bend left] node {0} (q1); \end{tikzpicture} \end{center} \end{frame} \begin{frame} \frametitle{NFA} \begin{definition}[Nicht-Deterministischer endlicher Automat] Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit \begin{itemize} \item $Q, \Sigma, q_0, F$ wie ein DFA \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \mapsto P(Q)$ \end{itemize} \end{definition} \vfill \pause \begin{center} \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] \node[state, initial] (q0) {$q_0$}; \node[state, accepting] (q1) [right of = q0] {$q_1$}; \draw[->] (q0) edge [loop above] node {0,1} (q0); \draw[->] (q0) edge node {1} (q1); \end{tikzpicture} \end{center} \end{frame} \begin{frame} \frametitle{$\epsilon$-NFA} \begin{definition}[NFA mit $\epsilon$-Übergängen] Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit \begin{itemize} \item $Q, \Sigma, q_0, F$ wie ein DFA \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \mapsto P(Q)$ \end{itemize} \end{definition} \vfill \pause \begin{center} \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=] \node[state] (q1) {$q_1$}; \node[state, initial] (q0) [left of = q1] {$q_0$}; \node[state, accepting] (q2) [right of = q1] {$q_2$}; \draw[->] (q0) edge [red] node {$\epsilon$} (q1); \draw[->] (q1) edge [loop above] node {0,1} (q1); \draw[->] (q1) edge node {1} (q2); \draw[->] (q0) edge [bend right, red] node {$\epsilon$} (q2); \end{tikzpicture} \end{center} \end{frame} \begin{frame} \frametitle{Automaten} \begin{block}{Übergangsfunktionen} Die Automaten $A = (Q, \Sigma, \delta, q_0, F)$ unterscheiden sich nur durch ihre Übergangsfunktionen. \begin{description} \item[DFA] $\delta : Q \times \Sigma \mapsto Q$ \item[NFA] $\delta : Q \times \Sigma \mapsto \alert{P(Q)}$ \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \mapsto \alert{P(Q)}$ \end{description} \end{block} \vfill \begin{theorem} \alert{DFA}, \alert{NFA} und \alert{$\epsilon$-NFA} sind gleich mächtig und lassen sich ineinander umwandeln. \end{theorem} \end{frame} \begin{frame} \frametitle{Tutoraufgabe 3} \begin{center} \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] \node[state, initial] (q0) {$q_0$}; \node[state, accepting] (q1) [above right of = q0] {$q_1$}; \node[state] (q2) [right of = q1] {$q_2$}; \node[state] (q3) [below right of = q0] {$q_3$}; \node[state] (q4) [right of = q3] {$q_4$}; \draw[->] (q0) edge node {0} (q1); \draw[->] (q0) edge node {1} (q3); \draw[->] (q1) edge [loop above] node {0} (q1); \draw[->] (q2) edge [loop right] node {1} (q2); \draw[->] (q4) edge [loop right] node {0} (q4); \draw[->] (q1) edge [bend left] node {1} (q2); \draw[->] (q2) edge [bend left] node {0} (q1); \draw[->] (q3) edge [bend left] node {0,1} (q4); \draw[->] (q4) edge [bend left] node {1} (q3); \end{tikzpicture} \end{center} \end{frame} \end{document}