Changeset 256 for liacs/TPFL2010/assignment3/report.tex

Timestamp:

Dec 16, 2010, 10:00:17 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Opdracht 5 met een beetje hulp van Wikipedia en cs.nyu.edu/courses/fall03/V22.0453-001/ans3.pdf

File:

• liacs/TPFL2010/assignment3/report.tex (modified) (3 diffs)

liacs/TPFL2010/assignment3/report.tex

@@ -46 +46 @@
 
 \section{Opgave 5.1}
-De gramatica $G$ bestaat uit de volgende producties:
-\begin{equation}
+De grammatica $G$ bestaat uit de volgende producties:
+\begin{equation*}
 \begin{array}{l}
 S \rightarrow AB \sep b \\
@@ -54 +54 @@
 C \rightarrow SS \sep a  \\
 \end{array}
-\end{equation}
+\end{equation*}
 
 Gebruikmakend van het CYK algoritme gaan we aantonen dat $x = babbbab \in L(G)$
 zit. De ondersteunende tabel is van de grootte $6\times6$ omdat dit de lengte
 van het woord $x$ is. In tabel~\ref{tb:opdr1} staat\footnote{Om de \LaTeX~tabel 
-automatisch te gegenereren vanuit een woord en een CFG gramatica heb ik
+automatisch te gegenereren vanuit een woord en een CFG grammatica heb ik
 \url{http://rickvanderzwet.nl/svn/personal/liacs/TPFL2010/assignment3/cyk.py}
 geschreven, vanwege de fouten ik met handwerk maakte.} cel $i,j$ voor welke
@@ -129 +129 @@
 
 \section{Opgave 5.5}
+Om een LL(1) grammatica te generen voor alle woorden in $\{w \in
+\{a,b\}^*~:~|w|_a = |w|_b\}$ is:
+\begin{equation*}
+S \rightarrow aSbS \sep bSaS \sep \emptyset
+\end{equation*}
+Om aan te tonen dat de grammatica correct is, is het eerst belangrijk om te
+zien dat elke keer dat een $a$ genereerd word er ook automatisch een $b$
+genereerd wordt. Deze dus altijd gelijk zijn. 
+Om te laten zien dat deze grammatica \emph{alle} woorden in de taal bevat is
+bewijzen we met inductie naar lengte van het woord. Als $|w| = 0$ dan is $w =
+\emptyset$, deze wordt door de taal herkent.
+
+Neem alle woorden tot lengte $2N$ en een gelijk aantal $a$ en $b$ afleidbaar
+zijn van $S$. Neem nu de string $w'$ met een gelijk aantal $a$ en $b$, een
+lengte van $2(N+1)$ en $a$ als begin symbool. In het slechte geval is $2N+2$
+weer nieuw woord doordat je altijd een extra $T$ kan ontwikkelen en die daarna
+laat terminereren. Bijvoorbeeld $abab \rightarrow abaSbS \rightarrow ababSaSbS
+\rightarrow ababab$. 
+
+In de betere gevallen bestaat er een $2 \le j \le 2N+2$ zodaning dat $j$
+aangeeft dat $w[1..j]$ een gelijk aantal $a$ en $b$ heeft, zodanig dat de vorm
+van $w' = aw_1bw_2$. Met inductie kunnen we bewijzen dat $w_1$ en $w_2$
+gemaakt kunnen worden van $S$, wat volgt dat $w'$ ook van $S$ gemaakt kan
+worden.