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

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

\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. De opgaven zijn
willekeurig gekozen met behulp van een kans generator, het kans dus zijn dat
niet alle onderwerpen 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
modelleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
(Q,\Sigma,\delta,q_0,F)$ die $L$ beschrijft.  Construeer 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 verdubbeld.
$voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
maar maak aanpassingen zodanig 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$ beschrijft $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]
gelijkheid 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 op-zich zijn, zal
alle elementen met elkaar vergeleken kunnen worden door middel van $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} exponentieel 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 gedefinieerd:
\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 variabele wordt gedefinieerd. 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}
\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}
\label{fig:idee}
\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}

Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' => `de klasse van
talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) => (a)]
aan de hand van het volgende voorbeeld:
Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q =
\{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden
die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die
hoger als $k$ genummerd zijn.

Om dit te doen is een recursieve formule nodig, welke $R_{i,j,k}$ als invoer
heeft. a) Kijk welke transities er mogelijk zijn in $\delta$ met toestand $i$ als
begin positie. Plaats deze op de `stapel'. b) Werk de elementen op de stapel
stuk voor stuk af volgens dezelfde methodiek. Stop pas als de $\delta$
resultaat $j$ bevat. Let erop dat oneindige herhalingen gedetecteerd moeten
worden om het algoritme te laten termineren. Je kan het zien als het volledig
doorzoeken van een boom met in de wortel de knoop $i$.

\section{Opgave 3.54}

Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en definieer:
\begin{equation}
L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\}
\end{equation}
Dit zijn dus de woorden waarbij alle elementen precies \'{e}\'{e}n keer in voor
komen. Bijvoorbeeld $L_3 = \{123,132,213,231,312,321\}$.

Om te laten zijn dat er minimal een reguliere expressie van lengte $2^{n-1}$
nodig is om $L_n$ te specificeren, moet de \emph{Myhill-Nerode} stelling
toegepast worden. Vanwege de eigenschap dat prefix uniek is, zat het nooit
mogelijk worden om aan beiden woorden hetzelfde toe te voegen zodanig dat ze in
elkaars klasse terecht komen. (elk `bit' informatie is relevant). Voor alle
klasse zal dus apart gekeken worden of aan de eisen voldaan wordt. Om dus alle
getallen $n$ van de string te controleren of zij uniek is zijn minimaal
$2^{n-1}$ toestanden nodig.

Echter voor $\overline{L_n}$  is wel een reguliere expressie te vinden en wel
in de grootte $O(n^2)$. Door simpelweg voor elke $i \in \Sigma^*$ een reguliere
expressie te maken van de vorm $x^*~i~x^*~i~x^*$ waarbij $x = Sigma^* - i$. 

\section{Opgave 3.68}

Voor een woord $w \in \Sigma^*$, is een palc($w$) de korte palindroom $x$
zodanig dat $w$ een prefix is van $x$. en palc($L$) = $\bigcup_{w \in L}\{palc(w)\}$.

Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$
waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$
is, moet er gebruik gemaakt worden van een tegenstelling. Als $w$ nog een
palindroom aan het einde zal bevatten $uu$, dan ziet $x$ er als volgt uit
$wuuuuw$, dit is niet de korte palindroom ($ww$), welke $uuuu$ er nog makkelijk
uit weggehaald had kunnen worden. Een willekeurige suffix van $w$ kan ook geen
palindroom vormen die nog `weggesneden' kan worden, omdat hij anders al in den
beginne een palindroom had moeten zijn.

Als $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke
`vertaling' van een woord $w$ naar zijn palc($w$). De nieuwe woorden zullen in
het slechtste geval evenveel blijven, maar de taal kan ook kleiner worden.

De andere kant op geldt dit \underline{niet}, als $L$ regulier is, dan is het
onbeslist of palc\textsuperscript{-1}($L$) ook regulier is. Het kan namelijk
zeer goed dat een (ingewikkelde) functie die woorden genereerde welke een
palindroom zijn en die aan een vast prefix ($p$) toegevoegd. De \emph{palc}
functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is.


\section{Opgave 3.69}

Laat $x_1,x_2,\ldots,x_k \in \Sigma^*$. Om te laten zien dat $\Sigma^* -
x_{1}^{*}x_{2}^{*} \cdots x_{k}^*$ eindig is dan en slechts als $|\Sigma| = 1$
en gcd($|x_1|,|x_2|,\ldots,|x_k|$) = 1 moet er een paar dingen bewezen worden
a) aantonen dat het \underline{niet} geldt voor de tegenvoorbeelden a) $gcd
> 1$ b) $|\Sigma| > 1$ en tevens moet aangetoond worden waarom de eindigheid
 voor dit specifieke geval geldt.

Merk op dat met een gcd van 1 alle getallen in de verzameling \{1,
priemgetallen\} zitten. Bij een alfabet van 1 letter hoeft er enkel maar
gesproken worden over lengtes. Standaard zitten alle lengtes in de taal.
Aangezien de `deel-lengtes' ($x_1,x_2,\ldots,x_k$) nul of meer keer in de
verzameling in de verzameling mogen zitten. Zal je uiteindelijk overblijven met
een eindige set lengtes. In het geval dat er lengte 1 gevonden wordt, zal zelfs
de lege set het antwoord zijn.

a) Als $|\Sigma| > 1$, bijvoorbeeld $\{1,2\}$ dan kan er een oneindige
verzameling gemaakt worden, door $x_1,x_2,\ldots,x_k \in 1^*$. De $2*$ zal dan een
oneindige verzameling vormen.

b) $gcd > 1$, bijvoorbeeld $2$ dan kan er een oneindige verzameling gemaakt
worden, doordat niet alle woorden gemaakt kunnen worden. Enkel worden van
`even' lengte in dit geval. Waardoor de `oneven' woorden een eindige string
gaan vormen. Bij grotere waardes ($r$) kunnen ook 'groepen' (de $|r|* - 1$)
bijvoorbeeld niet meer bereikt worden, welke dan tot een oneindige verzameling
kunnen groeien. 

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