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

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