Changeset 259

Timestamp:

Dec 17, 2010, 12:24:40 AM (14 years ago)

Author:

Rick van der Zwet

Message:

5.10 is een cadeautje van Rosenkrantz

Location:

liacs/TPFL2010/assignment3

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (3 diffs)

liacs/TPFL2010/assignment3/report.tex

@@ -181 +181 @@
 onze volgende stap (de $FIRST$) unique \footnote{De eigenschap wordt
 afgedwongen door Stelling 5.3.4 en de bovenstaande definitie op
-\cite{TPFL2010}[pg.~157]} zijn onafhankelijk wat hier achter wordt gezet.
+\cite{JS2009}[pg.~157]} zijn onafhankelijk wat hier achter wordt gezet.
 
 $\Leftarrow$ Als voor alle willekeurige $x$ en $y$ beiden in $FOLLOW(X)$ beiden
@@ -188 +188 @@
 \rightarrow \beta$ door elkaar te onderscheiden zijn door het eerste symbool.
 Omdat dit geldt voor alle transities is de taal dus herkenbaar door enkel het
-eerste symbool in de transities en dus LL(1).
-
-
-\section{Opgave 5.8}
+eerste symbool in de transities en dus LL(1). Als ze wel een gemeenschapelijk
+start symbool hebben zijn er minimaal 2 symbolen nodig om de taal te herkennen
+en is deze \underline{niet} LL(1).
+
+
+% \section{Opgave 5.8}
+% Een voorbeeld van een LR(0) grammatica waar er een levensvatbare prefix
+% $\gamma$ bestaat en \emph{item}\footnote{Ik kan geen goede vertaling voor item
+% vinden welke de definie \cite{JS2009}[pg.~145] eer aandoet} $A \rightarrow
+% \bullet, B \rightarrow \alpha \bullet \beta$ welke beiden geldig zijn voor
+% $\gamma$.
+\newpage
+\section{Opgave 5.10}
+Een voorbeeld van een grammatica welke wel $LL(k+1)$ is maar niet $LL(k)$, is gegeven in \cite{STOC69}[pg.~174] en is de grammatica van de taal $\{a^n(b^kd|b|cc)^n : n \ge 1\}$:
+\begin{equation}
+\begin{array}{l}
+S \rightarrow aSA \\
+S \rightarrow aA \\
+A \rightarrow cc \\
+A \rightarrow bB \\
+A \rightarrow \varepsilon \\
+B \rightarrow b^{k-1}d \\
+\end{array}
+\end{equation}
 
 
@@ -200 +220 @@
 \bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
 languages and automata theory }, \emph{Cambridge University Press}, 2009.
+\bibitem[STOC69]{STOC69}Rosenkrantz, D. J. and Stearns, R. E., Properties of
+deterministic top down grammars, Proceedings of the first annual
+ACM symposium on Theory of computing, STOC '69, Marina del Rey,
+California, United States, 165--180
 \end{thebibliography}
-\newpage
 \end{document}
+