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

%
% $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.
\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$
is gelijkt aan de oude acceptatie toestand.
\\
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 $xR_{l}y$ dan en slechts dan
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. 

De (triviale) taal $L = {01,10}$ is een voorbeeld hiervan. Beiden woorden hebben
hun eigen klasse. Als $x = 0$ en $y = 1$, bestaat er een $z = 1$, zodanig dat
$xz \in L, yz \notin L$.

De taal $M = \{{0}^* : |M|_0~is~een~priemgetal\}$  is een ander voorbeeld. Als we
kijken naar $aR_{l}b$ kan er altijd een $z$ gevormd worden zodanig dat $az \in
M, bz \notin M$. Bijvoorbeeld $a = 0^3, b =0^5, z = 0^4$. Deze eigenschap wordt
afgedwongen door het `feit' dat er geen relatie bestaat tussen de lengtes
tussen opeenvolgende priemgetallen.\footnote{Ik heb dit voor gemak aangenomen,
de praktijk is echter dat is nog een groot wiskundig vraagstuk is.}


\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 \le k,j,i_j \le 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 bij de plek $k$. 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. De aanpak kan als volgt gezien worden:
\begin{verbatim}
1. controleren of |1| <= 2de 0-reeks dmv 'knopen-strook' (knopen 0.X en 1.X).
2. |2| tellen onthouden dmv 'knopen-strook' (knopen 2.X).
3. naar gewenste locatie lopen (knopen 3.X).
4. |0| tellen onthouden dmv 'knopen-strook' (knopen 4.X).
5. naar begin 2de 0-reeks lopen (knopen 5.X).
6. 0-reeks vergelijken (knopen 6.X).
\end{verbatim}
Voor deze aanpak zijn 3 `knopen-stroken' nodig, 3 `transitie-lagen' en 1 controle
strook. In totaal dus in ongeveer $O(7n)$ knopen.  Figuur~\ref{fig:2dfa} laat
de \emph{2DFA} zien.


\begin{figure}
\center
\begin{tikzpicture}[node distance=20mm]
\node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q00) {0.0};
\node[place] (q01) [right=of q00] {0.1};
\node[place] (q02) [right=of q01] {0.2};
\node[place] (q03) [right=of q02] {0.3};
\node[place] (q10) [below=of q00] {1.0};
\node[place] (q11) [below=of q01] {1.1};
\node[place] (q12) [below=of q02] {1.2};
\node[place] (q13) [below=of q03] {1.3};
\node[place] (q20) [below=of q10] {2.0};
\node[place] (q21) [below=of q11] {2.1};
\node[place] (q22) [below=of q12] {2.2};

\node[place] (q30) [below=of q20] {3.0};
\node[place] (q31) [below=of q21] {3.1};
\node[place] (q32) [below=of q22] {3.2};
\node[place] (q33) [right=of q32] {3.3};

\node[place] (q40) [below=of q30] {4.0};
\node[place] (q41) [below=of q31] {4.1};
\node[place] (q42) [below=of q32] {4.2};

\node[place] (q50) [below=of q40] {5.0};
\node[place] (q51) [below=of q41] {5.1};
\node[place] (q52) [below=of q42] {5.2};
\node[place] (q53) [double,right=of q52] {5.3};

\node[place] (q60) [below=2cm of q50] {6.0};
\node[place] (q61) [below=2cm of q51] {6.1};
\node[place] (q62) [below=2cm of q52] {6.2};
\node[place] (q63) [right=of q62] {6.3};

\path[->] 
          (q00) edge               node[above] {3,R} (q01)
          (q01) edge               node[above] {1,R} (q02)
          (q01) edge [loop above]  node[above] {0,R} (q01)
          (q02) edge               node[above] {1,R} (q03)
          (q02) edge [loop above]  node[above] {0,R} (q02)
          (q03) edge [loop above]  node[above] {0,R} (q03)

          (q11) edge               node[above] {0,L} (q10)
          (q12) edge [bend left]   node[below] {0,L} (q10)
          (q13) edge [bend left]   node[below] {0,L} (q10)

          (q01) edge               node {2,R} (q11)
          (q02) edge               node {2,R} (q12)
          (q03) edge               node {2,R} (q13)
          (q13) edge               node[above] {2,R} (q12)
          (q12) edge               node[above] {2,R} (q11)

          (q10) edge               node {2,L} (q20)
          (q20) edge               node[below] {2,L} (q21)
          (q21) edge               node[below] {2,L} (q22)

          (q20) edge               node {0,L} (q30)
          (q21) edge               node {0,L} (q31)
          (q22) edge               node {0,L} (q32)

          (q30) edge               node {1,L} (q31)
          (q31) edge               node {1,L} (q32)
          (q32) edge [bend left]   node {3,R} (q33)
          (q32) edge [bend right]  node {1,R} (q33)

          (q30) edge [loop below]  node {0,L} (q30)
          (q31) edge [loop below]  node {0,L} (q31)
          (q32) edge [loop below]  node {0,L} (q32)

          (q33) edge [bend left]   node {0,R} (q42)
          (q42) edge               node {0,R} (q41)
          (q41) edge               node {0,R} (q40)

          (q40) edge [bend right]  node {2,R} (q60)
          (q40) edge               node {1,R} (q50)
          (q41) edge [bend right]  node {2,R} (q61)
          (q41) edge               node {1,R} (q51)
          (q42) edge [bend right]  node {2,R} (q62)
          (q42) edge               node {1,R} (q52)

          (q50) edge [loop below]  node {$\begin{array}{c}1,R\\0,R\end{array}$} (q50)
          (q51) edge [loop below]  node {$\begin{array}{c}1,R\\0,R\end{array}$} (q51)
          (q52) edge [loop below]  node {$\begin{array}{c}1,R\\0,R\end{array}$} (q52)
          (q50) edge [bend left,looseness=2]  node {2,R} (q60)
          (q51) edge [bend left,looseness=2]  node {2,R} (q61)
          (q52) edge [bend left,looseness=2]  node {2,R} (q62)
 
          (q60) edge               node {0,R} (q61)
          (q61) edge               node {0,R} (q62)
          (q62) edge               node {0,R} (q63)
          (q63) edge               node {4,R} (q53)
        ;
\end{tikzpicture}
\caption{Opdracht 2.22a uitgewerkt voor $1 \le n \le 3$. Niet geldige stappen zijn niet genoemd en moet voor compleetheidnaar een 'putje' knoop gestuurd worden. Uitbreiden kan door het expanderen van `traviale' knopen.}
\label{fig:2dfa}
\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.

Dit vertaald zich in een Myhill-Nerode relatie om het aantal toestanden te
kunnen bepalen. $F_p$ en $F_q$ waarbij $p < q, 1 \le p,q \le n$ is
onderscheidbaar, door voor $z=2*0*4$ te nemen, zodanig dat het woord door $F_q$
geaccepteerd wordt, maar niet door $F_p$, door $|z|_2 \ge p$ te kiezen.

Voor elke $F_i : 1 \ge i \ge n$ geldt dat deze `intern' ook $i^2$ unique
toestanden geeft. We splitsen de woorden bij $2$, zodat we over een `prefix' en
`suffix' kunnen praten. Een `prefix' past maar bij '{e}'{e}n `suffix'. De
`suffixes' die gegenereeerd worden van de vorm $2*0*4$, kan $i^2$ vormen
aannemen (bijvoorbeeld $i=2 {204,2004,22004,2204}$).
Deze unique suffixes zorgen ervoor dat de Myhill-Nerode toepassing een
substring $z$ kan vinden welke een van de unique suffixes bevat, waardoor het
`prefix' niet samenkomt met een `suffix'.

\section{Opgave 3.47}

Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' $\Rightarrow$ `de klasse van
talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) $\Rightarrow$ (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 dan $k$ genummerd zijn.


$R_{i,j,k}$ accepteert als $q_i \in q_1, q_j \in F$. 
Om $R_{i,j,k+1}$ te verkrijgen, nemen we eerst de toestanden van $R_{i,j,k}$,
deze verenigen we dan met alle toestanden die we vanuit $R_{i,j,k}$ kunnen
bereiken met een transities $\delta(a,k+1) : i \le a \le j$, die in een
\underline{nieuwe} toestand uitkomen, de lussen hebben geen meerwaarde voor ons
doel. De begin toestand is te markeren als $R_{i,j,0} = {q_1} : i = j = 1$.

\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\in \Sigma\}
\end{equation}
Dit zijn dus de woorden waarbij alle elementen van $\Sigma$ precies \'{e}\'{e}n keer voor
komen. Bijvoorbeeld $L_3 = \{123,132,213,231,312,321\}$.

a) Om te laten zijn dat er minimaal een reguliere expressie van lengte $2^{n-1}$
nodig is om $L_n$ te specificeren, passen we de \emph{Myhill-Nerode} stelling
toe. Neem $x,y \in \Sigma^*$. Als geldt $|x| = |y|$ en de elementen zijn
gelijk, maar enkel hun volgorde verschilt (bijvoorbeeld $123,132$) dan zitten
ze in dezelfde klasse. Voor $xR_{l}y$ als de lengte verschilt, dan is er een
$z$ te vinden zodanig dat $y$ wel geaccepteerd wordt en $x$ niet (bijvoorbeeld
voor $34,345$, is dit $12$), vanwege $|x| + a \neq = |y| + a = n$ desals $|x|
\neq |y|$. Als de `inhoud' verschilt maar de lengte gelijk is dan $z = \Sigma -
\{y\}$, omdat $\Sigma \backslash \{x\} \neq \Sigma \backslash \{y\}$.


b) Echter voor $\overline{L_n}$  is wel een reguliere expressie te vinden en wel
in de grootte $O(n^2)$. $\bigcup_{a : 0 .. n}{\bigcup_{i \in \Sigma_a}\{x^*ix^*ix^*\}}$  waarbij $x \in
(\Sigma_a \backslash \{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)\}$.

a) 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. Neem aan dat $w$ een
palindroom aan het einde zal bevatten $uu$ en dus van de vorm is $ruu$ dan ziet
palc($w$) er als volgt uit $ruuuur$, dit is niet de korte palindroom
($rr$), welke $uuuu$ er nog uit $x$ weggehaald had kunnen worden. 
Een willekeurige suffix van $w$ kan dus geen palindroom vormen die nog
`weggesneden' kan worden, omdat hij anders al in den beginne een palindroom had
moeten zijn. 
$t$ moet wel de \underline{langste} palindroom suffix van $w$ zijn, omdat
anders een `dubbele' palindroom problemen op gaat leveren. Neem bijvoorbeeld
$w$ van de vorm is $ruuyy$ als je van de palindroom $yy$ verwijderd, zal
palc($w$) = $ruuuur$. Dit is niet de kortste palindroom ($rr$).

b) Neem $L = \{ uvxyz : u,x,z \in 1^*~en~v,u \in 0^* \}$ en $\Sigma = \{0,1\}$.
De woorden die palc($L$) moeten bevatten zijn alle woorden van $L$ minus de
woorden $|x|_1 = even, |v|_0 = |y|_0, |u|_0 = |z|_0$. Die set komt niet door
het pumping lemma en is dus palc($L$) is \underline{niet} regulier.

c) Neem palc\textsuperscript{-1}($L$), dan is dit $\{ x \in L, u \in \Sigma^* :
xuu \}$, welke alle woorden zijn met hun prefix in $L$ en hun suffix is een
palindroom. Het genereren van palindromen met een reguliere taal is
\underline{niet} mogelijk, dus palc\textsuperscript{-1}($L$) is
\underline{niet} regulier.

\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\footnote{Ook paargewijs relatief priem genoemd, zie http://nl.wikipedia.org/wiki/Paarsgewijs\_relatief\_priem}, moeten beiden kanten op bekeken worden.


$\Rightarrow$: Door middel van een tegenstelling kunnen we bewijzen dat
$|\Sigma| = 1$ moet zijn. Neem $|\Sigma| > 1$ en $x_1,x_2,\ldots,x_n = 0$ dan
is deze oneindig, en wel in de vorm $(\Sigma \backslash {0})^*$. Door een
tweede tegenstelling tonen we aan dat de gcd \'{e}\'{e}n moet zijn.  Als $|\Sigma|
= 1$ en $g$ = gcd($|x_1|,|x_2|,\ldots,|x_n|$) $\neq$ 1 dan komen er enkel woorden
voor van lengte $g^n : n = 1 .. n$ Hierdoor zullen de woorden met lengte
$(g-1)^*$ een oneindige reeks vormen.

$\Leftarrow$: Doordat $|\Sigma| = 1$ is de lengte van de string indentiek aan
zijn formaat. Met een gcd($|x_1|,|x_2|,\ldots,|x_n|$) $\neq$ 1 kunnen we alle
bijna alle lengtes genereren door de eigenschap dat de nummers (relatief) priem
zijn.\footnote{Dit is een grote gok, aangenomen dat er een Stelling bestaat,
welke stelt dat je uit 2 priemgetallen vanaf een bepaald punt alle getallen kan
genereren.}

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