Mercurial > 14ss.theoinf

comparison notes/tex/grammars.tex @ 3:624c6e0e4383

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first slides
author Markus Kaiser <markus.kaiser@in.tum.de>
date Sun, 13 Apr 2014 20:22:34 +0200
parents a9275b863a0d
children e1b3b7b99d28
comparison
equal deleted inserted replaced
2:dcbc3181a802 3:624c6e0e4383
1 \defineUnit{grammatik}{% 1 \defineUnit{grammatik}{%
2 \begin{frame} 2 \begin{frame}
3 \frametitle{Grammatiken} 3 \frametitle{Grammatiken}
4 \setbeamercovered{dynamic} 4 \setbeamercovered{dynamic}
5 5
6 \begin{definition}[Kontextfreie Grammatik] 6 \begin{definition}[Grammatik]
7 Eine \alert{kontextfreie Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel: 7 Eine \structure{(Phrasenstruktur-)Grammatik} $G = (V, \Sigma, P, S)$ ist ein 4-Tupel:
8 \begin{description} 8 \begin{description}
9 \item[V] endlich viele \alert{Nichtterminale} (Variablen) 9 \item[V] endlich viele \alert{Nichtterminale} (Variablen)
10 \item[$\Sigma$] ein Alphabet von \alert{Terminalen} 10 \item[$\Sigma$] ein Alphabet von \alert{Terminalen}
11 \item[P] endlich viele \alert{Produktionen} $\subseteq V \times \left( V \cup \Sigma \right)^*$ 11 \item[P] endlich viele \alert{Produktionen} $\subseteq \left( V \cup \Sigma \right)^* \times \left( V \cup \Sigma \right)^*$
12 \item[S] ein \alert{Startsymbol} 12 \item[S] ein \alert{Startsymbol} (Axiom)
13 \end{description} 13 \end{description}
14 \end{definition} 14 Ist $(l, r) \in P$, so schreibt man \structure{$l \rightarrow r$}.
15 15 \end{definition}
16 \begin{example}[Vorbereitung 3] 16
17 \vfill
18
19 \begin{example}[]
17 $\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. 20 $\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.
18 \pause 21 \visible<2>{
19 \[ 22 \begin{align}
20 S \rightarrow 0S1 \mid S11 \mid 1 23 S \rightarrow 0S1 \mid S11 \mid 1
21 \] 24 \end{align}
25 }
22 \end{example} 26 \end{example}
23 \end{frame} 27 \end{frame}
24 } 28 }
25 29
26 \defineUnit{ableitung}{% 30 \defineUnit{ableitung}{%
27 \begin{frame} 31 \begin{frame}
28 \frametitle{Ableitungsrelation} 32 \frametitle{Ableitungsrelation}
29 \setbeamercovered{dynamic} 33 \setbeamercovered{dynamic}
30 34
31 \begin{definition}[Ableitungsrelation] 35 \begin{definition}[Ableitungsrelation]
32 Eine CFG $G$ induziert eine \alert{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$: 36 Eine Grammatik $G$ induziert eine \structure{Ableitungsrelation} $\rightarrow_G$ auf Wörtern über $V \cup \Sigma$. Seien $x, y$ solche Wörter und
33 \[ 37 \begin{align}
34 \alpha \rightarrow_G \beta 38 z &= x\alert{\alpha}y\\
35 \] 39 z^\prime &= x\alert{\beta}y\\
36 gdw es eine Regel $A \rightarrow \gamma$ in $P$ mit Wörtern $\alpha_1, \alpha_2$ gibt, so dass 40 \intertext{Dann ist}
37 \[ 41 z &\rightarrow_G z^\prime
38 \alpha = \alpha_1\alert{A}\alpha_2 \quad \text{und} \quad \beta = \alpha_1 \alert{\gamma} \alpha_2 42 \end{align}
39 \] 43 gdw. es eine Regel $\alert{\alpha \rightarrow \beta}$ in $P$ gibt.
40 \end{definition} 44 \end{definition}
41 45
42 \begin{example}[Vorbereitung 3] 46 \vfill
47
48 \begin{example}[]
43 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$: 49 Mit den Produktionen $S \rightarrow 0S1 \mid S11 \mid 1$:
44 \begin{align*} 50 \begin{align*}
45 S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\ 51 S &\rightarrow_G 0S1 \rightarrow_G 00S11 \rightarrow_G 00S1111 \rightarrow_G 0011111 \\
46 \Rightarrow S &\rightarrow_G^* 0011111 52 \intertext{Es gilt also}
53 S &\rightarrow_G^* 0011111
47 \end{align*} 54 \end{align*}
48 \end{example} 55 \end{example}
56 \end{frame}
57 }
58
59 \defineUnit{sprachtypen}{%
60 \begin{frame}
61 \frametitle{Sprachtypen}
62
63 Sei $G = (V, \Sigma, P, S)$ eine Grammatik und $\alpha \rightarrow \beta \in P$ beliebig.
64 \begin{definition}[Monotonie]
65 $G$ heißt \structure{(längen-)monoton}, wenn für $\alpha \neq S$ gilt
66 \begin{align}
67 \alert{\abs{\alpha} \leq \abs{\beta}}
68 \end{align}
69 und falls $S \to \epsilon \in P$, dann kommt $S$ nie auf der rechten Seite vor.
70 \end{definition}
71
72 \vfill
73
74 \begin{definition}[Chomsky-Typen]
75 Seien $A \in V$, $\gamma, \delta \in (V \cup \Sigma)^*$ und $\beta^\prime \in (V \cup \Sigma)^+$.\\
76 Damit $G$ vom \structure{Typ k} ist, muss für $\alpha$ und $\beta$ gelten
77 \begin{center}
78 \tabulinesep=4pt
79 \begin{tabu} to .8\textwidth{X[1,c,m]|[.5pt]X[2,c,m]X[2,c,m]}
80 & $\alpha$ & $\beta$\\\tabucline[.5pt]{-}
81 \structure{Typ 0} & beliebig & beliebig\\
82 \structure{Typ 1} & $= \alert{\gamma} A \alert{\delta}$ & $= \alert{\gamma} \beta^\prime \alert{\delta}$\\
83 \structure{Typ 2} & $\in V$ & beliebig\\
84 \structure{Typ 3} & $\in V$ & $\in \Sigma^+ \cup \Sigma^*V$\\
85 \end{tabu}
86 \end{center}
87 Ab Typ 1 muss $G$ auch \alert{monoton} sein.
88 \end{definition}
49 \end{frame} 89 \end{frame}
50 } 90 }
51 91
52 \defineUnit{cfl}{% 92 \defineUnit{cfl}{%
53 \begin{frame}[c] 93 \begin{frame}[c]