Ignore:
Timestamp:
Nov 10, 2010, 9:35:19 PM (14 years ago)
Author:
Rick van der Zwet
Message:

Answers to first assignment

File:
1 edited

Legend:

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

    r221 r224  
    88\usepackage[english,dutch]{babel}
    99\selectlanguage{dutch}
    10 \usepackage{graphicx}
     10\usepackage[pdftex]{graphicx}
    1111\usepackage{url}
    12 \usepackage{multicol}
    13 \usepackage{fancybox}
    1412\usepackage{amssymb,amsmath}
     13\usepackage{lipsum}
     14\usepackage{float}
    1515
    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}}
    1922\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>}}
    2724\date{\today}
    2825
     26
    2927\begin{document}
     28\newcommand{\DFA}{\emph{DFA}~}
     29\newcommand{\qed}{\hfill \ensuremath{\Box}}
     30\maketitle
     31\begin{abstract}
     32Dit 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}
    3036
    31 \maketitle
     37\section{Opgave 3.3}
     38Als $L \subseteq \Sigma^*$ is regulier dan is de taal
     39\begin{equation}
     402L := {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}
     42regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
     43modeleren 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$
     45die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
     46en 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$,
     48maar 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$
     50moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$.
    3251
    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}
     52De 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
     66languages and automata theory }, \emph{Cambridge University Press}, 2009.
    4167\end{thebibliography}
    4268\newpage
    43 % \advance\textwidth by 8cm
    44 % \advance\oddsidemargin by -3cm
    45 % \advance\evensidemargin by -3cm
    46 % \advance\topmargin by -2cm
    47 % \advance\textheight by 4cm
    48 % \advance\footskip by -4cm
    49 % \marginparwidth 0cm
    50 % \twocolumn
    51 % \section*{Appendix}
    52 % De NN code en pre-parse.pl code  zagen er als volgt uit:
    53 % \newline
    54 % \tiny
    55 % %preformatted with `source-highlight -n -f latex bridge.cc`
    56 % \input{nn.c}
    57 % \input{data/pre-parse.pl}
    58 % \onecolumn
    59 
    6069\end{document}
Note: See TracChangeset for help on using the changeset viewer.