|
31
|
1 \input{preamble.tex} |
|
23
|
2 |
|
|
3 \title{Übung 5: Kontextfreie Sprachen} |
|
|
4 \subtitle{Theoretische Informatik Sommersemester 2013} |
|
|
5 \author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} |
|
|
6 |
|
|
7 \begin{document} |
|
|
8 |
|
|
9 \begin{frame} |
|
|
10 \titlepage |
|
|
11 \end{frame} |
|
|
12 |
|
|
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} |
