Changeset 258

Timestamp:

Dec 16, 2010, 10:38:52 PM (14 years ago)

Author:

Rick van der Zwet

Message:

5.6 bla,bla,bla...

Location:

liacs/TPFL2010/assignment3

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (1 diff)

liacs/TPFL2010/assignment3/report.tex

@@ -175 +175 @@
 
 \section{Opgave 5.6}
+Laat $G$ een \emph{CFG} zijn zonder 'nutteloze symbolen. Als $G$ een LL(1) grammatica is dan en slechts als, voor willekeurig twee ongelijke producties van de vorm $X \rightarrow \alpha$ en $X \rightarrow \beta$, dan is het volgende geldig, als $x,y \in FOLLOW(X)$ dan $FIRST(\alpha x) \cap FIRST(\beta y) = \emptyset$. De symbolen $x$ en $y$ hoeven niet unique te zijn.
+
+$\Rightarrow$ Als $G$ LL(1) dan moet met behulp van '{e}'{e} symbool de juiste
+transitie gekozen worden. Als we bijvoorbeeld in toestand $X$ zijn dan moet
+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.
+
+$\Leftarrow$ Als voor alle willekeurige $x$ en $y$ beiden in $FOLLOW(X)$ beiden
+geen gemeenschapelijke start symbool hebben ($FIRST(\alpha x) \cap FIRST(\beta
+y) = \emptyset$), betekend dat de transities $X \rightarrow \alpha$ en $X
+\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).