Mercurial > 14ss.theoinf
comparison notes/tex/grammars.tex @ 22:334369297f54
fix compilation error; fix errors in gnf construction; start suppliing complete notes
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Fri, 16 May 2014 17:34:00 +0200 |
| parents | 6a3cdddedcf7 |
| children | 7afd6762980f |
comparison
equal
deleted
inserted
replaced
| 21:6a3cdddedcf7 | 22:334369297f54 |
|---|---|
| 474 \frametitle{Linksrekursive Produktionen} | 474 \frametitle{Linksrekursive Produktionen} |
| 475 | 475 |
| 476 \begin{definition}[Linksrekursive Produktion] | 476 \begin{definition}[Linksrekursive Produktion] |
| 477 Man nennt eine Produktion \structure{linksrekursiv}, wenn sie die Form | 477 Man nennt eine Produktion \structure{linksrekursiv}, wenn sie die Form |
| 478 \[ | 478 \[ |
| 479 \structure{A} \to \structure{A}\alpha_1 \mid \dots \mid \structure{A}\alpha_k \mid \beta_i \mid \dots \mid \beta_l \quad \text{mit} \quad \alpha_i, \beta_i \in \left( V \cup \Sigma \right)^+ | 479 \structure{A} \to \structure{A}\alpha_1 \mid \dots \mid \structure{A}\alpha_k \mid \beta_1 \mid \dots \mid \beta_l \quad \text{mit} \quad \alpha_i, \beta_i \in \left( V \cup \Sigma \right)^+ |
| 480 \] | 480 \] |
| 481 hat, wobei die $\beta_i$ nicht mit $A$ beginnen. | 481 hat, wobei die $\beta_i$ nicht mit $A$ beginnen. |
| 482 \end{definition} | 482 \end{definition} |
| 483 | 483 |
| 484 \vfill | 484 \vfill |
| 509 \end{block} | 509 \end{block} |
| 510 | 510 |
| 511 \vspace{1em} | 511 \vspace{1em} |
| 512 | 512 |
| 513 \only<2> { | 513 \only<2> { |
| 514 Benenne alle Nichtterminale \structure{beliebig} um in $A_1, \dots, A_\abs{V}$. | 514 Benenne alle Nichtterminale \structure{beliebig} um in $A_1, \dots, A_{\abs{V}}$. |
| 515 \begin{align} | 515 \begin{align} |
| 516 S &\rightarrow Ab, \quad A \rightarrow aAS \mid \epsilon \\ | 516 S &\rightarrow Ab, \quad A \rightarrow aAS \mid \epsilon \\ |
| 517 \intertext{wird zu} | 517 \intertext{wird zu} |
| 518 A_1 &\to A_2b\\ | 518 A_1 &\to A_2b\\ |
| 519 A_2 &\to aA_2A_1 | 519 A_2 &\to aA_2A_1 |
| 525 \begin{itemize} | 525 \begin{itemize} |
| 526 \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r < l$}, dann setze \structure{$A_r$} in $A_l$ ein. | 526 \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r < l$}, dann setze \structure{$A_r$} in $A_l$ ein. |
| 527 \only<3> { | 527 \only<3> { |
| 528 \begin{align} | 528 \begin{align} |
| 529 A_1 &\to A_2 \mid a \mid b \\ | 529 A_1 &\to A_2 \mid a \mid b \\ |
| 530 A_2 &\to \structure{A_1}xA_1 | 530 A_2 &\to \structure{A_1}A_1 |
| 531 \intertext{wird zu} | 531 \intertext{wird zu} |
| 532 A_1 &\to a \mid b\\ | 532 A_1 &\to a \mid b\\ |
| 533 A_2 &\to \structure{A_2}xA_1 \mid \structure{a}xA_1 \mid \structure{b}xA_1 | 533 A_2 &\to \structure{A_2}A_1 \mid \structure{a}A_1 \mid \structure{b}A_1 |
| 534 \end{align} | 534 \end{align} |
| 535 } | 535 } |
| 536 \item Entferne danach alle \structure{linksrekursiven} $A_l$-Produktionen. | 536 \item Entferne danach alle \structure{linksrekursiven} $A_l$-Produktionen. |
| 537 \only<4> { | 537 \only<4> { |
| 538 \begin{align} | 538 \begin{align} |
| 539 A_2 &\to A_2\structure{xA_1} \mid \alert{axA_1} \mid \alert{bxA_1} | 539 A_2 &\to A_2\structure{A_1} \mid \alert{aA_1} \mid \alert{bA_1} |
| 540 \intertext{wird zu} | 540 \intertext{wird zu} |
| 541 A_2 &\to \alert{axA_1} \mid \alert{bxA_1} \mid \alert{axA_1}A_3 \mid \alert{bxA_1}A_3\\ | 541 A_2 &\to \alert{aA_1} \mid \alert{bA_1} \mid \alert{aA_1}A_3 \mid \alert{bA_1}A_3\\ |
| 542 A_3 &\to \structure{xA_1} \mid \structure{xA_1}A_3 | 542 A_3 &\to \structure{A_1} \mid \structure{A_1}A_3 |
| 543 \end{align} | 543 \end{align} |
| 544 } | 544 } |
| 545 \end{itemize} | 545 \end{itemize} |
| 546 } | 546 } |
| 547 | 547 |
| 549 Betrachte alle Produktionen $A_l \to \dots$ in \structure{absteigender Reihenfolge}.\\ | 549 Betrachte alle Produktionen $A_l \to \dots$ in \structure{absteigender Reihenfolge}.\\ |
| 550 \begin{itemize} | 550 \begin{itemize} |
| 551 \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r > l$}, dann setze \structure{$A_r$} in $A_l$ ein. | 551 \item Existieren Produktionen der Form $A_l \to \structure{A_r}\alpha$ mit \alert{$r > l$}, dann setze \structure{$A_r$} in $A_l$ ein. |
| 552 \begin{align} | 552 \begin{align} |
| 553 A_1 &\to a \mid b \mid \structure{A_2} \\ | 553 A_1 &\to a \mid b \mid \structure{A_2} \\ |
| 554 A_2 &\to axA_1 \mid bxA_1 \mid axA_1A_3 \mid bxA_1A_3\\ | 554 A_2 &\to aA_1 \mid bA_1 \mid aA_1A_3 \mid bA_1A_3\\ |
| 555 A_3 &\to xA_1 \mid xA_1A_3 | 555 A_3 &\to bA_3 \mid c |
| 556 \intertext{$A_1$ wird zu} | 556 \intertext{$A_1$ wird zu} |
| 557 A_1 &\to a \mid b \mid \structure{axA_1} \mid \structure{bxA_1} \mid \structure{axA_1A_3} \mid \structure{bxA_1A_3} | 557 A_1 &\to a \mid b \mid \structure{aA_1} \mid \structure{bA_1} \mid \structure{aA_1A_3} \mid \structure{bA_1A_3} |
| 558 \end{align} | 558 \end{align} |
| 559 \end{itemize} | 559 \end{itemize} |
| 560 | 560 |
| 561 } | 561 } |
| 562 \end{frame} | 562 \end{frame} |