Ignore:
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:
1 edited

Legend:

Unmodified
Added
Removed
  • liacs/TPFL2010/assignment3/report.tex

    r255 r256  
    4646
    4747\section{Opgave 5.1}
    48 De gramatica $G$ bestaat uit de volgende producties:
    49 \begin{equation}
     48De grammatica $G$ bestaat uit de volgende producties:
     49\begin{equation*}
    5050\begin{array}{l}
    5151S \rightarrow AB \sep b \\
     
    5454C \rightarrow SS \sep a  \\
    5555\end{array}
    56 \end{equation}
     56\end{equation*}
    5757
    5858Gebruikmakend van het CYK algoritme gaan we aantonen dat $x = babbbab \in L(G)$
    5959zit. De ondersteunende tabel is van de grootte $6\times6$ omdat dit de lengte
    6060van het woord $x$ is. In tabel~\ref{tb:opdr1} staat\footnote{Om de \LaTeX~tabel
    61 automatisch te gegenereren vanuit een woord en een CFG gramatica heb ik
     61automatisch te gegenereren vanuit een woord en een CFG grammatica heb ik
    6262\url{http://rickvanderzwet.nl/svn/personal/liacs/TPFL2010/assignment3/cyk.py}
    6363geschreven, vanwege de fouten ik met handwerk maakte.} cel $i,j$ voor welke
     
    129129
    130130\section{Opgave 5.5}
     131Om een LL(1) grammatica te generen voor alle woorden in $\{w \in
     132\{a,b\}^*~:~|w|_a = |w|_b\}$ is:
     133\begin{equation*}
     134S \rightarrow aSbS \sep bSaS \sep \emptyset
     135\end{equation*}
     136Om aan te tonen dat de grammatica correct is, is het eerst belangrijk om te
     137zien dat elke keer dat een $a$ genereerd word er ook automatisch een $b$
     138genereerd wordt. Deze dus altijd gelijk zijn.
     139Om te laten zien dat deze grammatica \emph{alle} woorden in de taal bevat is
     140bewijzen we met inductie naar lengte van het woord. Als $|w| = 0$ dan is $w =
     141\emptyset$, deze wordt door de taal herkent.
     142
     143Neem alle woorden tot lengte $2N$ en een gelijk aantal $a$ en $b$ afleidbaar
     144zijn van $S$. Neem nu de string $w'$ met een gelijk aantal $a$ en $b$, een
     145lengte van $2(N+1)$ en $a$ als begin symbool. In het slechte geval is $2N+2$
     146weer nieuw woord doordat je altijd een extra $T$ kan ontwikkelen en die daarna
     147laat terminereren. Bijvoorbeeld $abab \rightarrow abaSbS \rightarrow ababSaSbS
     148\rightarrow ababab$.
     149
     150In de betere gevallen bestaat er een $2 \le j \le 2N+2$ zodaning dat $j$
     151aangeeft dat $w[1..j]$ een gelijk aantal $a$ en $b$ heeft, zodanig dat de vorm
     152van $w' = aw_1bw_2$. Met inductie kunnen we bewijzen dat $w_1$ en $w_2$
     153gemaakt kunnen worden van $S$, wat volgt dat $w'$ ook van $S$ gemaakt kan
     154worden.
    131155
    132156
Note: See TracChangeset for help on using the changeset viewer.