% % $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{}} \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'). 2. |2| tellen (onthouden dmv 'knopen-strook', dit is `variable' A). 3. naar begin lopen. 4. A-1 '1' instanties laten passeren. 5. |0| tellen (onthouden dmv 'knopen-strook'm dit is `variable' A). 6. naar begin 2de 0-reeks lopen. 7. 0-reeks vergelijken. \end{verbatim} Voor deze aanpak zijn 3 `knopen-stroken' nodig en 3 transitie-lagen. In totaal dus in ongeveer $O(6n)$ knopen. Figuur~\ref{fig:2dfa} laat de \emph{2DFA} zien. \begin{figure} \center \begin{tikzpicture} \node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q00) {}; \node[place] (q01) [right=of q00] {}; \node[place] (q02) [right=of q01] {}; \node[place] (q03) [right=of q02] {}; \node[place] (q11) [below=of q01] {}; \node[place] (q12) [below=of q02] {}; \node[place] (q13) [below=of q03] {}; \node[place] (q10) [below=of q00] {}; \node[place] (q20) [below=of q10] {}; \node[place] (q21) [below=of q11] {}; \node[place] (q22) [below=of q12] {}; %\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} (q00) (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) % (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{Opdracht 2.22a uitgewerkt voor $n = 3$, niet geldige stappen zijn niet genoemd en moet allen naar een 'trap' knoop gestuurd worden} \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. \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}