source: liacs/TPFL2010/assignment3/report.tex@ 258

Last change on this file since 258 was 258, checked in by Rick van der Zwet, 14 years ago

5.6 bla,bla,bla...

File size: 9.4 KB
Line 
1%
2% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
3%
4
5\documentclass[12pt,a4paper]{article}
6
7\frenchspacing
8\usepackage[english,dutch]{babel}
9\selectlanguage{dutch}
10\usepackage[pdftex]{graphicx}
11\usepackage{url}
12\usepackage{amssymb,amsmath}
13\usepackage{float}
14\usepackage{tikz}
15\usepackage{fixltx2e}
16\usepackage{rotating}
17
18\usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}
19
20
21
22\setlength\parindent{0pt}
23\setlength\parskip{\baselineskip}
24\floatstyle{ruled}
25\newfloat{algoritm}{thp}{lop}
26\floatname{algoritm}{Algoritme}
27
28\title{Opdracht 3 \\
29\large{Topics on Parsing and Formal Languages - fall 2010}}
30\author{Rick van der Zwet\\
31 \texttt{<hvdzwet@liacs.nl>}}
32\date{\today}
33
34
35\begin{document}
36\newcommand{\DFA}{\emph{DFA}~}
37\newcommand{\qed}{\hfill \ensuremath{\Box}}
38\newcommand{\all}{\Sigma^*}
39\newcommand{\sep}{~|~}
40\maketitle
41\begin{abstract}
42Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
43\cite{JS2009} gebruikt bij het college. In deze opdracht zullen vijf opgaven
44(1, 5, 6, 8, 14) van hoofdstuk 5 behandeld worden.
45\end{abstract}
46
47\section{Opgave 5.1}
48De grammatica $G$ bestaat uit de volgende producties:
49\begin{equation*}
50\begin{array}{l}
51S \rightarrow AB \sep b \\
52A \rightarrow BC \sep a \\
53B \rightarrow AS \sep CB \sep b \\
54C \rightarrow SS \sep a \\
55\end{array}
56\end{equation*}
57
58Gebruikmakend van het CYK algoritme gaan we aantonen dat $x = babbbab \in L(G)$
59zit. De ondersteunende tabel is van de grootte $6\times6$ omdat dit de lengte
60van het woord $x$ is. In tabel~\ref{tb:opdr1} staat\footnote{Om de \LaTeX~tabel
61automatisch te gegenereren vanuit een woord en een CFG grammatica heb ik
62\url{http://rickvanderzwet.nl/svn/personal/liacs/TPFL2010/assignment3/cyk.py}
63geschreven, vanwege de fouten ik met handwerk maakte.} cel $i,j$ voor welke
64transities er gevolgt moet worden om het
65subwoord $x[i..j]$ te vormen. Omdat de start transitie $S$ in $1,6$ staat zit
66het woord $x$ in $L(G)$. De ontleedboom is te zien in figuur~\ref{fig:opdr1}.
67
68
69\begin{sidewaystable}[htbp]
70\center
71\begin{tabular}{|c||c|c|c|c|c|c|c|}
72\hline
73i\textbackslash j & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline \hline
74 1 & \begin{tabular}{l} S \\B \\ \end{tabular} & \begin{tabular}{l} A: (B,C,1) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,1) \\S: (A,B,2) \\B: (A,S,2) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,1) \\B: (C,B,3) \\C: (S,S,3) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,1) \\S: (A,B,2),(A,B,4) \\A: (B,C,3) \\B: (A,S,4),(C,B,4) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,5) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,1),(B,C,3),(B,C,4) \\C: (S,S,1),(S,S,5) \\S: (A,B,2),(A,B,4)\\...(A,B,5),(A,B,6) \\B: (A,S,2),(C,B,3)\\...(A,S,4),(C,B,4),(A,S,5)\\...(C,B,5),(A,S,6) \\ \end{tabular} \\ \hline
75 2 & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} A \\C \\ \end{tabular} & \begin{tabular}{l} S: (A,B,2) \\B: (A,S,2),(C,B,2) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,3) \\ \end{tabular} & \begin{tabular}{l} S: (A,B,2) \\B: (C,B,2),(C,B,4) \\A: (B,C,3) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,5) \\ \end{tabular} & \begin{tabular}{l} S: (A,B,2),(A,B,5),(A,B,6) \\B: (A,S,2),(C,B,2),\\...(C,B,4),(A,S,5),(A,S,6) \\A: (B,C,3) \\C: (S,S,5) \\ \end{tabular} \\ \hline
76 3 & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} S \\B \\ \end{tabular} & \begin{tabular}{l} C: (S,S,3) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,3) \\B: (C,B,4) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,5) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,3) \\B: (C,B,4),(A,S,5),(A,S,6) \\S: (A,B,5),(A,B,6) \\ \end{tabular} \\ \hline
77 4 & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} S \\B \\ \end{tabular} & \begin{tabular}{l} C: (S,S,4) \\ \end{tabular} & \begin{tabular}{l} $\emptyset$ \end{tabular} & \begin{tabular}{l} A: (B,C,4) \\C: (S,S,4) \\B: (C,B,5) \\ \end{tabular} \\ \hline
78 5 & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} S \\B \\ \end{tabular} & \begin{tabular}{l} A: (B,C,5) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,5) \\S: (A,B,6) \\B: (A,S,6) \\ \end{tabular} \\ \hline
79 6 & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} A \\C \\ \end{tabular} & \begin{tabular}{l} S: (A,B,6) \\B: (A,S,6),(C,B,6) \\ \end{tabular} \\ \hline
80 7 & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} \end{tabular} & \begin{tabular}{l} S \\B \\ \end{tabular} \\ \hline
81
82\end{tabular}
83\caption{$CYK(L(G),a)$. Algoritme beschreven in \cite{JS2009}[pg.~142]}
84\label{tb:opdr1}
85\end{sidewaystable}
86
87\begin{figure}
88\center
89\begin{tikzpicture}
90 [level distance=10mm,level/.style={sibling distance=40mm/#1}]
91 \node {S}
92 child {node {A}
93 child {node {B}
94 child {node {b}}
95 }
96 child {node {C}
97 child {node {a}}
98 }
99 }
100 child {node {B}
101 child {node {C}
102 child {node {S}
103 child {node {S}
104 child {node {b}
105 }
106 }
107 child {node {S}
108 child {node {b}}
109 }
110 }
111 child {node {S}
112 child {node {b}}
113 }
114 }
115 child {node {B}
116 child {node {A}
117 child {node {a}}
118 }
119 child {node {S}
120 child {node {b}}
121 }
122 }
123 }
124 ;
125\end{tikzpicture}
126\label{fig:opdr1}
127\caption{Ontleedboom voor het woord $babbbab$}
128\end{figure}
129
130\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.
155
156LL(1) eigenschap wordt bereikt, door naar de \emph{FIRST} te kijken, welke
157respectivelijk $\{a\}, \{b\}, \{\emptyset\}$ zijn. De $FOLLOW(S) =
158\{a,b,\emptyset\}$. Deze twee gegevens samen maken dat de LL(1) bereikt wordt,
159welke ook te zijn is in tabel~\ref{tb:opdr5}.
160
161\begin{table}
162\center
163\begin{tabular}{c||c|c|c}
164y \textbackslash x & a & b & \$ \\
165\hline \hline
166S & $S \rightarrow aSbS$ & $S \rightarrow bSaS$ & $S \rightarrow \emptyset$ \\
167a & pop & & \\
168b & & pop & \\
169\# & & & accept \\
170\end{tabular}
171\caption{Ontleedtabel for Opdracht 5.5}
172\label{tb:opdr5}
173\end{table}
174
175
176\section{Opgave 5.6}
177Laat $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.
178
179$\Rightarrow$ Als $G$ LL(1) dan moet met behulp van '{e}'{e} symbool de juiste
180transitie gekozen worden. Als we bijvoorbeeld in toestand $X$ zijn dan moet
181onze volgende stap (de $FIRST$) unique \footnote{De eigenschap wordt
182afgedwongen door Stelling 5.3.4 en de bovenstaande definitie op
183\cite{TPFL2010}[pg.~157]} zijn onafhankelijk wat hier achter wordt gezet.
184
185$\Leftarrow$ Als voor alle willekeurige $x$ en $y$ beiden in $FOLLOW(X)$ beiden
186geen gemeenschapelijke start symbool hebben ($FIRST(\alpha x) \cap FIRST(\beta
187y) = \emptyset$), betekend dat de transities $X \rightarrow \alpha$ en $X
188\rightarrow \beta$ door elkaar te onderscheiden zijn door het eerste symbool.
189Omdat dit geldt voor alle transities is de taal dus herkenbaar door enkel het
190eerste symbool in de transities en dus LL(1).
191
192
193\section{Opgave 5.8}
194
195
196\section{Opgave 5.14}
197
198
199\begin{thebibliography}{1}
200\bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
201languages and automata theory }, \emph{Cambridge University Press}, 2009.
202\end{thebibliography}
203\newpage
204\end{document}
Note: See TracBrowser for help on using the repository browser.