Mercurial > 14ss.theoinf
changeset 3:624c6e0e4383
first slides
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Sun, 13 Apr 2014 20:22:34 +0200 |
| parents | dcbc3181a802 |
| children | bc52346d79d8 |
| files | notes/tex/automatons.tex notes/tex/computation.tex notes/tex/frames.tex notes/tex/grammars.tex notes/tex/preamble.tex notes/tex/ue01_notes.tex |
| diffstat | 6 files changed, 103 insertions(+), 42 deletions(-) [+] |
line wrap: on
line diff
--- a/notes/tex/automatons.tex Sun Apr 13 17:11:29 2014 +0200 +++ b/notes/tex/automatons.tex Sun Apr 13 20:22:34 2014 +0200 @@ -14,9 +14,9 @@ \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$ + \item $\alert{AB} \defeq \left\{ uv \mid u \in A \wedge v \in B \right\}$ + \item $\alert{A^n} \defeq \left\{w_1 \ldots w_n \mid w_1 \ldots w_n \in A \right\}$,\qquad $A^0 \defeq \{\epsilon\}$ + \item $\alert{A^*} \defeq \bigcup_{n \in \N_0} A^n$ \end{itemize} \end{definition} \end{frame}
--- a/notes/tex/computation.tex Sun Apr 13 17:11:29 2014 +0200 +++ b/notes/tex/computation.tex Sun Apr 13 20:22:34 2014 +0200 @@ -152,11 +152,11 @@ \tikzstyle{rect} = [thick]; \tikzstyle{caption} = [align=left, anchor=north west]; - \chomsky{tumblue}{}{0}{Berechenbare Funktionen}; - \chomsky{tumred}{dashed}{1}{Typ 0 - Rekursiv aufzählbar\\Turingmaschinen, $\lambda$-Kalkül}; - \chomsky{tumivory}{}{2}{Typ 1 - Kontextsensitiv\\CSG}; - \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\PDA, CFG}; - \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\DFA, RE}; + \chomsky{tumlightblue}{}{0}{Alle formalen Sprachen}; + \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik}; + \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik}; + \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal}; + \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik}; \end{tikzpicture} \end{center} \end{frame}
--- a/notes/tex/frames.tex Sun Apr 13 17:11:29 2014 +0200 +++ b/notes/tex/frames.tex Sun Apr 13 20:22:34 2014 +0200 @@ -12,26 +12,31 @@ \frametitle{Organisatorisches} \begin{itemize} - \item Mail: \href{mailto:tutor@zfix.org}{tutor@zfix.org} - \item Web: \href{theo.zfix.org}{theo.zfix.org} - \item Hg: \href{tutor.zfix.org}{tutor.zfix.org} - \vfill - \item Wann? + \item Markus Kaiser \begin{itemize} - \item Dienstag 10:15-11:45 00.08.038 - \item Dienstag 12:10-13:45 00.08.038 + \item Mail: \href{mailto:tutor@zfix.org}{tutor@zfix.org} + \item Web: \href{theo.zfix.org}{theo.zfix.org} + \item Hg: \href{tutor.zfix.org}{tutor.zfix.org} \end{itemize} - %\item Übungsablauf, Aufgabentypen + \vfill + \item Meine Übungen + \begin{itemize} + \item Gruppe 04: Montag, 16:15 - 17:45, 03.09.012 + \item Gruppe 15: Donnerstag, 10:15 - 11:45, 00.08.038 + \end{itemize} + \vspace{0.5em} \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 + \item Abgabe am Mittwoch, 10h + \item Rückgabe in der Übung + \item \alert{Kein Notenbonus} + \item Trotzdem machen! \end{itemize} + \vspace{0.5em} \item Klausur \begin{itemize} - \item Endterm: Mi 31.07. 11.30-14h - \item Wiederholung: Do 26.09. 11-13.30h + \item Endterm: Do 24.07. 11-14h + \item Wiederholung: Do 25.09. 11-14h \end{itemize} \end{itemize} \end{frame}
--- a/notes/tex/grammars.tex Sun Apr 13 17:11:29 2014 +0200 +++ b/notes/tex/grammars.tex Sun Apr 13 20:22:34 2014 +0200 @@ -3,22 +3,26 @@ \frametitle{Grammatiken} \setbeamercovered{dynamic} - \begin{definition}[Kontextfreie Grammatik] - Eine \alert{kontextfreie Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel: + \begin{definition}[Grammatik] + Eine \structure{(Phrasenstruktur-)Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel: \begin{description} \item[V] endlich viele \alert{Nichtterminale} (Variablen) \item[$\Sigma$] ein Alphabet von \alert{Terminalen} - \item[P] endlich viele \alert{Produktionen} $\subseteq V \times \left( V \cup \Sigma \right)^*$ - \item[S] ein \alert{Startsymbol} + \item[P] endlich viele \alert{Produktionen} $\subseteq \left( V \cup \Sigma \right)^* \times \left( V \cup \Sigma \right)^*$ + \item[S] ein \alert{Startsymbol} (Axiom) \end{description} + Ist $(l, r) \in P$, so schreibt man \structure{$l \rightarrow r$}. \end{definition} - \begin{example}[Vorbereitung 3] + \vfill + + \begin{example}[] $\Sigma = \left\{ 0, 1 \right\}$. Grammatik für alle Wörter ungerader Länge, bei denen alle Nullen vor der ersten Eins stehen und weniger Nullen als Einsen vorhanden sind. - \pause - \[ - S \rightarrow 0S1 \mid S11 \mid 1 - \] + \visible<2>{ + \begin{align} + S \rightarrow 0S1 \mid S11 \mid 1 + \end{align} + } \end{example} \end{frame} } @@ -29,26 +33,62 @@ \setbeamercovered{dynamic} \begin{definition}[Ableitungsrelation] - Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$: - \[ - \alpha \rightarrow_G \beta - \] - gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass - \[ - \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2 - \] + Eine Grammatik $G$ induziert eine \structure{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$. Seien $x, y$ solche Wörter und + \begin{align} + z &= x\alert{\alpha}y\\ + z^\prime &= x\alert{\beta}y\\ + \intertext{Dann ist} + z &\rightarrow_G z^\prime + \end{align} + gdw. es eine Regel $\alert{\alpha \rightarrow \beta}$ in $P$ gibt. \end{definition} - \begin{example}[Vorbereitung 3] + \vfill + + \begin{example}[] Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: \begin{align*} S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\ - \Rightarrow S &\rightarrow_G^* 0011111 + \intertext{Es gilt also} + S &\rightarrow_G^* 0011111 \end{align*} \end{example} \end{frame} } +\defineUnit{sprachtypen}{% +\begin{frame} + \frametitle{Sprachtypen} + + Sei $G = (V, \Sigma, P, S)$ eine Grammatik und $\alpha \rightarrow \beta \in P$ beliebig. + \begin{definition}[Monotonie] + $G$ heißt \structure{(längen-)monoton}, wenn für $\alpha \neq S$ gilt + \begin{align} + \alert{\abs{\alpha} \leq \abs{\beta}} + \end{align} + und falls $S \to \epsilon \in P$, dann kommt $S$ nie auf der rechten Seite vor. + \end{definition} + + \vfill + + \begin{definition}[Chomsky-Typen] + Seien $A \in V$, $\gamma, \delta \in (V \cup \Sigma)^*$ und $\beta^\prime \in (V \cup \Sigma)^+$.\\ + Damit $G$ vom \structure{Typ k} ist, muss für $\alpha$ und $\beta$ gelten + \begin{center} + \tabulinesep=4pt + \begin{tabu} to .8\textwidth{X[1,c,m]|[.5pt]X[2,c,m]X[2,c,m]} + & $\alpha$ & $\beta$\\\tabucline[.5pt]{-} + \structure{Typ 0} & beliebig & beliebig\\ + \structure{Typ 1} & $= \alert{\gamma} A \alert{\delta}$ & $= \alert{\gamma} \beta^\prime \alert{\delta}$\\ + \structure{Typ 2} & $\in V$ & beliebig\\ + \structure{Typ 3} & $\in V$ & $\in \Sigma^+ \cup \Sigma^*V$\\ + \end{tabu} + \end{center} + Ab Typ 1 muss $G$ auch \alert{monoton} sein. + \end{definition} +\end{frame} +} + \defineUnit{cfl}{% \begin{frame}[c] \frametitle{Kontextfreie Sprache}
--- a/notes/tex/preamble.tex Sun Apr 13 17:11:29 2014 +0200 +++ b/notes/tex/preamble.tex Sun Apr 13 20:22:34 2014 +0200 @@ -1,4 +1,5 @@ \documentclass[compress, 9pt, german, t]{beamer} +\usepackage{etex} \usepackage[ngerman]{babel} \uselanguage{German} @@ -30,7 +31,6 @@ \mathtoolsset{showonlyrefs,showmanualtags} \usepackage{mathrsfs} \usepackage{csquotes} -\usepackage{wasysym} \usepackage{beamerthemeLEA2} \setbeamercovered{transparent} @@ -82,5 +82,5 @@ \tikzstyle{machine} = [rectangle, draw, minimum width=2cm, minimum height=1cm, inner sep=3mm, fill=tumgreen!10] \newcommand{\pcp}[2]{ \begin{tabu}{c} #1 \\ \tabucline{-} #2 \\ \end{tabu} } -\newcommand{\chomsky}[4]{\draw[rect, #1, fill=#1!10, #2] ({5.5 - #3 * 1}, {0 + #3 * 0.3}) rectangle ({-5.5 + #3 * 1}, {7 - #3 * 1.2}) node[caption] {#4};} +\newcommand{\chomsky}[4]{\draw[rect, #1, fill=#1!10, #2] ({5.5 - #3 * 0.5}, {0 + #3 * 0.3}) rectangle ({-5.5 + #3 * 0.5}, {7 - #3 * 1.2}) node[caption] {#4};} \newcommand{\langclass}[4]{\draw[rect, #1, fill=#1!20, #2] ({5.2 - #3 * 0.5}, {0 + #3 * 0.12}) rectangle ({-5.2 + #3 * 0.5}, {7.5 - #3 * 0.75}) node[caption] {#4};}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue01_notes.tex Sun Apr 13 20:22:34 2014 +0200 @@ -0,0 +1,16 @@ +\input{preamble.tex} +\input{frames.tex} + +\title{Übung 1: Sprachen und Grammatiken} +\subtitle{Theoretische Informatik Sommersemester 2014} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} +\showUnit{titel} +\showUnit{organisatorisches} +\showUnit{wasisttheo} +\showUnit{alphabet} +\showUnit{grammatik} +\showUnit{sprachtypen} +\showUnit{chomsky} +\end{document}