% % $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' (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}