Changeset 260

Timestamp:

Dec 17, 2010, 1:00:33 AM (14 years ago)

Author:

Rick van der Zwet

Message:

5.14 done!

Location:

liacs/TPFL2010/assignment3

Files:

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

liacs/TPFL2010/assignment3/report.tex

@@ -201 +201 @@
 \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}
+Een voorbeeld van een grammatica welke wel $LL(k+1)$ is maar niet $LL(k)$, is
+gegeven in context van het aantonen dat voor elke $k > 0$ de $L(k+1)$ talen
+niet de $L(k)$ talen zijn. \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 \\
@@ -208 +211 @@
 A \rightarrow cc \\
 A \rightarrow bB \\
-A \rightarrow \varepsilon \\
+A \rightarrow \epsilon \\
 B \rightarrow b^{k-1}d \\
 \end{array}
-\end{equation}
+\end{equation*}
 
 
 \section{Opgave 5.14}
+Laat $G$ een LR(0) grammatica zijn met $A \rightarrow \alpha \bullet, \alpha
+\ne \epsilon$, welke geldig is voor een levensvatbare prefix $\gamma$ er geen
+enkel ander \emph{item} kan geldig zijn voor $\gamma$. Als er een \emph{item}
+van de vorm $A \rightarrow \alpha B$ is levert dit een shift-reduce error op.
+Als er een \emph{item} van de vorm $A \rightarrow \beta \bullet : \alpha \ne
+\beta$ zal het betekenen dat er een \emph{item} 'vooraf' aan gegaan $A
+\rightarrow \bullet \alpha$ \underline{en} $A \rightarrow \bullet \beta$, wat
+niet mogelijk is omdat enkel de eerste geldig kan zijn per definitie.