source: liacs/TPFL2010/assignment1/report.tex@ 225

%
% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{amssymb,amsmath}
\usepackage{lipsum}
\usepackage{float}

\floatstyle{ruled}
\newfloat{algoritm}{thp}{lop}
\floatname{algoritm}{Algoritme}

\title{Opdracht 1 \\
\large{Topics on Parsing and Formal Languages - fall 2010}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}}
\date{\today}


\begin{document}
\newcommand{\DFA}{\emph{DFA}~}
\newcommand{\qed}{\hfill \ensuremath{\Box}}
\maketitle
\begin{abstract}
Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
\cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
(3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden.
\end{abstract}

\section{Opgave 3.3}
Als $L \subseteq \Sigma^*$ is regulier dan is de taal
\begin{equation}
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
\end{equation}
regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
modeleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
(Q,\Sigma,\delta,q_0,F)$ die $L$ beschijft.  Construreer nu een nieuwe \DFA $P$
die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeled.
$voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
maar maak aanpassingen zodaning dat de nieuwe toestanden ook gelezen worden. Dus
$\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$
moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$.

De nieuwe \DFA $P$ beschijft $2L$ en dus is $2L$ regulier.
\qed


\section{Opgave 3.20}
Laat $\Sigma = {0,1}$ zijn. Een voorbeeld van de taal $L \subseteq
\Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
gelijkheids relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
eigen equivalentie klasse is, is de taal $L = {0,1}^+$.

\section{Opgave 3.22}
\section{Opgave 3.47}
\section{Opgave 3.54}
\section{Opgave 3.68}
\section{Opgave 3.69}

\begin{thebibliography}{1}
\bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
languages and automata theory }, \emph{Cambridge University Press}, 2009.
\end{thebibliography}
\newpage
\end{document}