Changeset 259 for liacs/TPFL2010/assignment3/report.tex
- Timestamp:
- Dec 17, 2010, 12:24:40 AM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/TPFL2010/assignment3/report.tex
r258 r259 181 181 onze volgende stap (de $FIRST$) unique \footnote{De eigenschap wordt 182 182 afgedwongen door Stelling 5.3.4 en de bovenstaande definitie op 183 \cite{ TPFL2010}[pg.~157]} zijn onafhankelijk wat hier achter wordt gezet.183 \cite{JS2009}[pg.~157]} zijn onafhankelijk wat hier achter wordt gezet. 184 184 185 185 $\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. 189 189 Omdat dit geldt voor alle transities is de taal dus herkenbaar door enkel het 190 eerste symbool in de transities en dus LL(1). 191 192 193 \section{Opgave 5.8} 190 eerste symbool in de transities en dus LL(1). Als ze wel een gemeenschapelijk 191 start symbool hebben zijn er minimaal 2 symbolen nodig om de taal te herkennen 192 en is deze \underline{niet} LL(1). 193 194 195 % \section{Opgave 5.8} 196 % Een voorbeeld van een LR(0) grammatica waar er een levensvatbare prefix 197 % $\gamma$ bestaat en \emph{item}\footnote{Ik kan geen goede vertaling voor item 198 % vinden welke de definie \cite{JS2009}[pg.~145] eer aandoet} $A \rightarrow 199 % \bullet, B \rightarrow \alpha \bullet \beta$ welke beiden geldig zijn voor 200 % $\gamma$. 201 \newpage 202 \section{Opgave 5.10} 203 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\}$: 204 \begin{equation} 205 \begin{array}{l} 206 S \rightarrow aSA \\ 207 S \rightarrow aA \\ 208 A \rightarrow cc \\ 209 A \rightarrow bB \\ 210 A \rightarrow \varepsilon \\ 211 B \rightarrow b^{k-1}d \\ 212 \end{array} 213 \end{equation} 194 214 195 215 … … 200 220 \bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal 201 221 languages and automata theory }, \emph{Cambridge University Press}, 2009. 222 \bibitem[STOC69]{STOC69}Rosenkrantz, D. J. and Stearns, R. E., Properties of 223 deterministic top down grammars, Proceedings of the first annual 224 ACM symposium on Theory of computing, STOC '69, Marina del Rey, 225 California, United States, 165--180 202 226 \end{thebibliography} 203 \newpage204 227 \end{document} 228
Note:
See TracChangeset
for help on using the changeset viewer.