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

%
% $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{float}
\usepackage{tikz}

\usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}



\setlength\parindent{0pt}
\setlength\parskip{\baselineskip}
\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. Dit wilt zeggen dat voor alle $z \in \Sigma^*$,
is er een $xz \in L$ dan en slechts als $yz \in L$. Omdat hier gezocht wordt
naar een taal waarbij de woorden allemaal equivalentie klassen opzich zijn, zal
alle elementen met elkaar vergeleken kunnen worden dmv $R_L$ en hier mogen geen
positieve 'gevallen' uitkomen. 

Een mooi voorbeeld is de taal van \emph{PRIMES2}\cite{JS2009}[pg. 2], waarbij
de priemgetallen in een binair stelsel worden vertegenwoordigd. Door op unieke
'start' van de woorden zullen deze nooit in elkaar vervallen en zal dus elk
woord zijn eigen klasse zijn.


\section{Opgave 3.22}
Om aan te tonen dat een \emph{2DFA} exponentioneel meer expressief is dan een
\DFA voor bepaalde talen kijken we naar de volgende taal; Laat $n$ een integer
$\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefineerd:
\begin{equation}
  F_n = \{3~0^{i_1}~1~0^{i_2} \cdots 1~0^{i_n}~2^k~0^{i_k}~4 : 1 \ge k,j,i_j \ge n\}
\end{equation}

Als eerste kan de $F_n$ door een \emph{2DFA} van $O(n)$ toestanden geaccepteerd
worden, welke aan te tonen is door eerst te kijken naar de eigenschappen van
$F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i^k$ zowel voor als na
de $2^k$ moet voorkomen. Waarbij $2^k$ aangeeft, waar deze $0$-reeks gevonden
kan worden e.g. bij welke $i_x$. De \emph{2DFA} moet dus twee dingen doen. Het
aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de
tweede plek variable wordt gedefineerd. Dit lijkt mij controleren op twee los
staande feiten. Hiervoor heb ik \underline{geen} antwoord gevonden. Ik kan
enkel wat voor $O(n^2)$ bedenken, welke een idee is in Figuur~\ref{fig:idee}
uitgewerkt is.


\begin{figure}
\label{fig:idee}
\center
\begin{tikzpicture}
\node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q0) {};
\node[place] (q1) [below=of q0] {};
\node[place] (q2) [below=of q1] {};
\node[place,pin={[pin edge={style=-<,thick,decorate,decoration={snake, pre length=4pt}}]below:}] (q3) [below=of q2] {};
\node[place] (q01) [right=3cm of q1] {};
\node[place] (q02) [right=3cm of q2] {};
\path[->] 
          (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q1)
          (q1) edge              node[left] {2} (q2)
          (q2) edge              node[left] {2} (q3)
          (q1) edge [decorate,decoration={snake}] node[above] {0-length-check} (q01)
          (q2) edge [decorate,decoration={snake}] node[above] {0-length-check} (q02)
        ;
\end{tikzpicture}
\caption{Idee voor Opdracht 2.22a}
\end{figure}

Om te laten zien dat een \DFA minstens $n^n$ toestanden nodig heeft moet je
gebruik maken van het feit dan een \DFA niet terug kan lopen. Het zal dus een
`geheugen' moeten maken om het maximale $0$ woord voor de `splitsing' ($2^k$)
te kunnen onthouden om zo te kijken of het overeen komt het $0$ woord na de
`splitsing'. Omdat je voor elke $F_i$ waarbij $1 \ge i \ge n$ minimaal $n$
toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
bestaan, heb je dus minimaal $n^n$ toestanden nodig.




\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}