Changeset 224 for liacs/TPFL2010/assignment1/report.tex
- Timestamp:
- Nov 10, 2010, 9:35:19 PM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/TPFL2010/assignment1/report.tex
r221 r224 8 8 \usepackage[english,dutch]{babel} 9 9 \selectlanguage{dutch} 10 \usepackage {graphicx}10 \usepackage[pdftex]{graphicx} 11 11 \usepackage{url} 12 \usepackage{multicol}13 \usepackage{fancybox}14 12 \usepackage{amssymb,amsmath} 13 \usepackage{lipsum} 14 \usepackage{float} 15 15 16 \author{Rick van der Zwet, Universiteit Leiden} 17 \title{XXX \\ 18 \large{XXX}} 16 \floatstyle{ruled} 17 \newfloat{algoritm}{thp}{lop} 18 \floatname{algoritm}{Algoritme} 19 20 \title{Opdracht 1 \\ 21 \large{Topics on Parsing and Formal Languages - fall 2010}} 19 22 \author{Rick van der Zwet\\ 20 \texttt{<hvdzwet@liacs.nl>}\\ 21 \\ 22 LIACS\\ 23 Leiden University\\ 24 Niels Bohrweg 1\\ 25 2333 CA Leiden\\ 26 The Netherlands} 23 \texttt{<hvdzwet@liacs.nl>}} 27 24 \date{\today} 28 25 26 29 27 \begin{document} 28 \newcommand{\DFA}{\emph{DFA}~} 29 \newcommand{\qed}{\hfill \ensuremath{\Box}} 30 \maketitle 31 \begin{abstract} 32 Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek 33 \cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven 34 (3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden. 35 \end{abstract} 30 36 31 \maketitle 37 \section{Opgave 3.3} 38 Als $L \subseteq \Sigma^*$ is regulier dan is de taal 39 \begin{equation} 40 2L := {a_1,a_1,a_2,a_2,\ldots,a_k,a_k}~:~elke~a_i \in \Sigma~en~a_1a_2{\cdots}a_k \in L 41 \end{equation} 42 regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de 43 modeleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M = 44 (Q,\Sigma,\delta,q_0,F)$ die $L$ beschijft. Construreer nu een nieuwe \DFA $P$ 45 die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$), 46 en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeled. 47 $voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$, 48 maar maak aanpassingen zodaning dat de nieuwe toestanden ook gelezen worden. Dus 49 $\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$ 50 moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$. 32 51 33 \section{Inleiding} 34 \section{Uitleg probleem} 35 \section{Theorie} 36 \section{Aanpak} 37 \section{Implementatie} 38 \section{Experimenten} 39 \section{Conclusie} 40 \begin{thebibliography}{10} 52 De nieuwe \DFA $P$ beschijft $2L$ en dus is $2L$ regulier. 53 \qed 54 55 56 57 \section{Opgave 3.20} 58 \section{Opgave 3.22} 59 \section{Opgave 3.47} 60 \section{Opgave 3.54} 61 \section{Opgave 3.68} 62 \section{Opgave 3.69} 63 64 \begin{thebibliography}{1} 65 \bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal 66 languages and automata theory }, \emph{Cambridge University Press}, 2009. 41 67 \end{thebibliography} 42 68 \newpage 43 % \advance\textwidth by 8cm44 % \advance\oddsidemargin by -3cm45 % \advance\evensidemargin by -3cm46 % \advance\topmargin by -2cm47 % \advance\textheight by 4cm48 % \advance\footskip by -4cm49 % \marginparwidth 0cm50 % \twocolumn51 % \section*{Appendix}52 % De NN code en pre-parse.pl code zagen er als volgt uit:53 % \newline54 % \tiny55 % %preformatted with `source-highlight -n -f latex bridge.cc`56 % \input{nn.c}57 % \input{data/pre-parse.pl}58 % \onecolumn59 60 69 \end{document}
Note:
See TracChangeset
for help on using the changeset viewer.