Mercurial > 13ss.theoinf

comparison notes/tex/ue05_notes.tex @ 44:15351d87ce76

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
transition notes
author Markus Kaiser <markus.kaiser@in.tum.de>
date Thu, 11 Jul 2013 22:06:26 +0200
parents 90ffda7e20c7
children
comparison
equal deleted inserted replaced
43:c14b92bfa07f 44:15351d87ce76
1 \input{preamble.tex} 1 \input{preamble.tex}
2 \input{frames.tex}
2 3
3 \title{Übung 5: Kontextfreie Sprachen} 4 \title{Übung 5: Kontextfreie Sprachen}
4 \subtitle{Theoretische Informatik Sommersemester 2013} 5 \subtitle{Theoretische Informatik Sommersemester 2013}
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} 6 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}}
6 7
7 \begin{document} 8 \begin{document}
8 9 \showUnit{titel}
9 \begin{frame} 10 \showUnit{grammatik}
10 \titlepage 11 \showUnit{ableitung}
11 \end{frame} 12 \showUnit{cfl}
12 13 \showUnit{induktivesprachdefinition}
13 \begin{frame}
14 \frametitle{Grammatiken}
15 \setbeamercovered{dynamic}
16
17 \begin{definition}[Kontextfreie Grammatik]
18 Eine \alert{kontextfreie Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel:
19 \begin{description}
20 \item[V] endlich viele \alert{Nichtterminale} (Variablen)
21 \item[$\Sigma$] ein Alphabet von \alert{Terminalen}
22 \item[P] endlich viele \alert{Produktionen} $\subseteq V \times \left( V \cup \Sigma \right)^*$
23 \item[S] ein \alert{Startsymbol}
24 \end{description}
25 \end{definition}
26
27 \begin{example}[Vorbereitung 3]
28 $\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.
29 \pause
30 \[
31 S \rightarrow 0S1 \mid S11 \mid 1
32 \]
33 \end{example}
34 \end{frame}
35
36 \begin{frame}
37 \frametitle{Ableitungsrelation}
38 \setbeamercovered{dynamic}
39
40 \begin{definition}[Ableitungsrelation]
41 Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$:
42 \[
43 \alpha \rightarrow_G \beta
44 \]
45 gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass
46 \[
47 \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2
48 \]
49 \end{definition}
50
51 \begin{example}[Vorbereitung 3]
52 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
53 \begin{align*}
54 S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\
55 \Rightarrow S &\rightarrow_G^* 0011111
56 \end{align*}
57 \end{example}
58 \end{frame}
59
60 \begin{frame}[c]
61 \frametitle{Kontextfreie Sprache}
62 \setbeamercovered{dynamic}
63
64 \begin{definition}[Kontextfreie Sprache]
65 Eine kontextfreie Grammatik $G = (V, \Sigma, P, S)$ \alert{erzeugt} die Sprache
66 \[
67 L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\}
68 \]
69 Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$.
70 \end{definition}
71
72 \end{frame}
73
74 \begin{frame}
75 \frametitle{Induktive Sprachdefinition}
76 \setbeamercovered{dynamic}
77
78 \begin{block}{Induktive Sprachdefinition}
79 Die \alert{induktive Definition} ($\Longrightarrow$) erzeugt Wörter \alert{bottom-up}, setzt also kleine Wörter zu größeren zusammen.
80 \end{block}
81
82 \begin{example}[Vorbereitung 3]
83 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
84
85 \begin{align*}
86 1 &\in L_G(S) \\
87 u \in L_G(S) \quad \Longrightarrow \quad 0\alert{u}1 &\in L_G(S) \\
88 u \in L_G(S) \quad \Longrightarrow \quad \alert{u}11 &\in L_G(S)
89 \end{align*}
90
91 Also z.B:
92
93 \[
94 1 \in L_G(S) \Longrightarrow 0\alert{1}0 \in L_G(S) \Longrightarrow \alert{010}11 \in L_G(S)
95 \]
96 \end{example}
97 \end{frame}
98
99 \end{document} 14 \end{document}