Mercurial > 14ss.theoinf
comparison notes/tex/grammars.tex @ 19:d9096d761fab
whitespace
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Wed, 14 May 2014 21:56:25 +0200 |
| parents | 1359f5a6aa60 |
| children | 02e25244ae1f |
comparison
equal
deleted
inserted
replaced
| 18:1359f5a6aa60 | 19:d9096d761fab |
|---|---|
| 99 \[ | 99 \[ |
| 100 L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\} | 100 L(G) := \left\{ w \in \Sigma^* \mid S \rightarrow_G^* w \right\} |
| 101 \] | 101 \] |
| 102 Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$. | 102 Eine Sprache $L \subseteq \Sigma^*$ heißt \alert{kontextfrei} gdw es eine kontextfreie Grammatik $G$ gibt mit $L = L(G)$. |
| 103 \end{definition} | 103 \end{definition} |
| 104 \end{frame} | 104 \end{frame} |
| 105 } | 105 } |
| 106 | 106 |
| 107 \defineUnit{induktivesprachdefinition}{% | 107 \defineUnit{induktivesprachdefinition}{% |
| 108 \begin{frame} | 108 \begin{frame} |
| 109 \frametitle{Induktive Sprachdefinition} | 109 \frametitle{Induktive Sprachdefinition} |
| 170 \end{definition} | 170 \end{definition} |
| 171 | 171 |
| 172 \vfill | 172 \vfill |
| 173 | 173 |
| 174 \begin{theorem} | 174 \begin{theorem} |
| 175 Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit | 175 Zu \alert{jeder} CFG $G$ existiert eine CFG $G'$ in Chomsky-Normalform mit |
| 176 \[ | 176 \[ |
| 177 L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}} | 177 L(G') = L(G) \alert{\setminus \left\{ \epsilon \right\}} |
| 178 \] | 178 \] |
| 179 \end{theorem} | 179 \end{theorem} |
| 180 \end{frame} | 180 \end{frame} |
| 388 | 388 |
| 389 \begin{align*} | 389 \begin{align*} |
| 390 V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ | 390 V_{ii} &= \left\{ A \in V \mid (A \rightarrow a_i) \in P \right\} \\ |
| 391 V_{ij} &= \left\{ A \in V \mid \exists k, B \in V_{ik}, C \in V_{k+1,j} \;.\; (A \rightarrow BC) \in P \right\} | 391 V_{ij} &= \left\{ A \in V \mid \exists k, B \in V_{ik}, C \in V_{k+1,j} \;.\; (A \rightarrow BC) \in P \right\} |
| 392 \end{align*} | 392 \end{align*} |
| 393 \end{frame} | 393 \end{frame} |
| 394 } | 394 } |
| 395 | 395 |
| 396 \defineUnit{cykbeispiel}{% | 396 \defineUnit{cykbeispiel}{% |
| 397 \begin{frame} | 397 \begin{frame} |
| 398 \frametitle{CYK} | 398 \frametitle{CYK} |
| 548 \end{itemize} | 548 \end{itemize} |
| 549 \begin{table} | 549 \begin{table} |
| 550 \begin{tabu}to \textwidth{X[c]|ccccc} | 550 \begin{tabu}to \textwidth{X[c]|ccccc} |
| 551 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} | 551 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} |
| 552 REG & ja & ja & ja & ja & ja\\ | 552 REG & ja & ja & ja & ja & ja\\ |
| 553 CFL & nein & ja & nein & ja & ja | 553 CFL & nein & ja & nein & ja & ja |
| 554 \end{tabu} | 554 \end{tabu} |
| 555 \end{table} | 555 \end{table} |
| 556 | 556 |
| 557 \begin{itemize} | 557 \begin{itemize} |
| 558 \item \alert{Entscheidbarkeit} | 558 \item \alert{Entscheidbarkeit} |