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

Last change on this file since 248 was 248, checked in by Rick van der Zwet, 14 years ago

4.47

File size: 14.8 KB
Line 
1%
2% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
3%
4
5\documentclass[12pt,a4paper]{article}
6
7\frenchspacing
8\usepackage[english,dutch]{babel}
9\selectlanguage{dutch}
10\usepackage[pdftex]{graphicx}
11\usepackage{url}
12\usepackage{amssymb,amsmath}
13\usepackage{float}
14\usepackage{tikz}
15\usepackage{fixltx2e}
16
17\usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}
18
19
20
21\setlength\parindent{0pt}
22\setlength\parskip{\baselineskip}
23\floatstyle{ruled}
24\newfloat{algoritm}{thp}{lop}
25\floatname{algoritm}{Algoritme}
26
27\title{Opdracht 1 \\
28\large{Topics on Parsing and Formal Languages - fall 2010}}
29\author{Rick van der Zwet\\
30 \texttt{<hvdzwet@liacs.nl>}}
31\date{\today}
32
33
34\begin{document}
35\newcommand{\DFA}{\emph{DFA}~}
36\newcommand{\qed}{\hfill \ensuremath{\Box}}
37\maketitle
38\begin{abstract}
39Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
40\cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
41(3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden.
42\end{abstract}
43
44\section{Opgave 3.3}
45Als $L \subseteq \Sigma^*$ is regulier dan is de taal
46\begin{equation}
472L := {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
48\end{equation}
49regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
50modelleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
51(Q,\Sigma,\delta,q_0,F)$ die $L$ beschrijft. Construeer nu een nieuwe \DFA $P$
52die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
53en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeld.
54$voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
55maar maak aanpassingen zodanig dat de nieuwe toestanden ook gelezen worden. Dus
56$\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$
57is gelijkt aan de oude acceptatie toestand.
58\\
59De nieuwe \DFA $P$ beschrijft $2L$ en dus is $2L$ regulier.
60\qed
61
62
63\section{Opgave 3.20}
64Laat $\Sigma = \{0,1\}$ zijn. Een voorbeeld van de taal $L \subseteq
65\Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
66gelijkheid relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
67eigen equivalentie klasse is. Dit wilt zeggen dat $xR_{l}y$ dan en slechts dan
68voor alle $z \in \Sigma^*$, is er een $xz \in L$ dan en slechts als $yz \in L$.
69Omdat hier gezocht wordt naar een taal waarbij de woorden allemaal equivalentie
70klassen op-zich zijn, zal alle elementen met elkaar vergeleken kunnen worden
71door middel van $R_L$ en hier mogen geen positieve 'gevallen' uitkomen.
72
73De (triviale) taal $L = {01,10}$ is een voorbeeld hiervan. Beiden woorden hebben
74hun eigen klasse. Als $x = 0$ en $y = 1$, bestaat er een $z = 1$, zodanig dat
75$xz \in L, yz \notin L$.
76
77De taal $M = \{{0}^* : |M|_0~is~een~priemgetal\}$ is een ander voorbeeld. Als we
78kijken naar $aR_{l}b$ kan er altijd een $z$ gevormd worden zodanig dat $az \in
79M, bz \notin M$. Bijvoorbeeld $a = 0^3, b =0^5, z = 0^4$. Deze eigenschap wordt
80afgedwongen door het `feit' dat er geen relatie bestaat tussen de lengtes
81tussen opeenvolgende priemgetallen.\footnote{Ik heb dit voor gemak aangenomen,
82de praktijk is echter dat is nog een groot wiskundig vraagstuk is.}
83
84
85\section{Opgave 3.22*}
86Om aan te tonen dat een \emph{2DFA} exponentieel meer expressief is dan een
87\DFA voor bepaalde talen kijken we naar de volgende taal; Laat $n$ een integer
88$\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefinieerd:
89\begin{equation}
90 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\}
91\end{equation}
92
93Als eerste kan de $F_n$ door een \emph{2DFA} van $O(n)$ toestanden geaccepteerd
94worden, welke aan te tonen is door eerst te kijken naar de eigenschappen van
95$F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i_k$ zowel voor als na
96de $2^k$ moet voorkomen. Waarbij $2^k$ aangeeft, waar deze $0$-reeks gevonden
97kan worden bij de plek $k$. De \emph{2DFA} moet dus twee dingen doen. Het
98aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de
99tweede plek variabele wordt gedefinieerd. De aanpak kan als volgt gezien worden:
100\begin{verbatim}
1011. controleren of |1| <= 2de 0-reeks dmv 'knopen-strook' (knopen 0.X en 1.X).
1022. |2| tellen onthouden dmv 'knopen-strook' (knopen 2.X).
1033. naar gewenste locatie lopen (knopen 3.X).
1044. |0| tellen onthouden dmv 'knopen-strook' (knopen 4.X).
1055. naar begin 2de 0-reeks lopen (knopen 5.X).
1066. 0-reeks vergelijken (knopen 6.X).
107\end{verbatim}
108Voor deze aanpak zijn 3 `knopen-stroken' nodig, 3 `transitie-lagen' en 1 controle
109strook. In totaal dus in ongeveer $O(7n)$ knopen. Figuur~\ref{fig:2dfa} laat
110de \emph{2DFA} zien.
111
112
113\begin{figure}
114\center
115\begin{tikzpicture}[node distance=20mm]
116\node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q00) {0.0};
117\node[place] (q01) [right=of q00] {0.1};
118\node[place] (q02) [right=of q01] {0.2};
119\node[place] (q03) [right=of q02] {0.3};
120\node[place] (q10) [below=of q00] {1.0};
121\node[place] (q11) [below=of q01] {1.1};
122\node[place] (q12) [below=of q02] {1.2};
123\node[place] (q13) [below=of q03] {1.3};
124\node[place] (q20) [below=of q10] {2.0};
125\node[place] (q21) [below=of q11] {2.1};
126\node[place] (q22) [below=of q12] {2.2};
127
128\node[place] (q30) [below=of q20] {3.0};
129\node[place] (q31) [below=of q21] {3.1};
130\node[place] (q32) [below=of q22] {3.2};
131\node[place] (q33) [right=of q32] {3.3};
132
133\node[place] (q40) [below=of q30] {4.0};
134\node[place] (q41) [below=of q31] {4.1};
135\node[place] (q42) [below=of q32] {4.2};
136
137\node[place] (q50) [below=of q40] {5.0};
138\node[place] (q51) [below=of q41] {5.1};
139\node[place] (q52) [below=of q42] {5.2};
140\node[place] (q53) [double,right=of q52] {5.3};
141
142\node[place] (q60) [below=2cm of q50] {6.0};
143\node[place] (q61) [below=2cm of q51] {6.1};
144\node[place] (q62) [below=2cm of q52] {6.2};
145\node[place] (q63) [right=of q62] {6.3};
146
147\path[->]
148 (q00) edge node[above] {3,R} (q01)
149 (q01) edge node[above] {1,R} (q02)
150 (q01) edge [loop above] node[above] {0,R} (q01)
151 (q02) edge node[above] {1,R} (q03)
152 (q02) edge [loop above] node[above] {0,R} (q02)
153 (q03) edge [loop above] node[above] {0,R} (q03)
154
155 (q11) edge node[above] {0,L} (q10)
156 (q12) edge [bend left] node[below] {0,L} (q10)
157 (q13) edge [bend left] node[below] {0,L} (q10)
158
159 (q01) edge node {2,R} (q11)
160 (q02) edge node {2,R} (q12)
161 (q03) edge node {2,R} (q13)
162 (q13) edge node[above] {2,R} (q12)
163 (q12) edge node[above] {2,R} (q11)
164
165 (q10) edge node {2,L} (q20)
166 (q20) edge node[below] {2,L} (q21)
167 (q21) edge node[below] {2,L} (q22)
168
169 (q20) edge node {0,L} (q30)
170 (q21) edge node {0,L} (q31)
171 (q22) edge node {0,L} (q32)
172
173 (q30) edge node {1,L} (q31)
174 (q31) edge node {1,L} (q32)
175 (q32) edge [bend left] node {3,R} (q33)
176 (q32) edge [bend right] node {1,R} (q33)
177
178 (q30) edge [loop below] node {0,L} (q30)
179 (q31) edge [loop below] node {0,L} (q31)
180 (q32) edge [loop below] node {0,L} (q32)
181
182 (q33) edge [bend left] node {0,R} (q42)
183 (q42) edge node {0,R} (q41)
184 (q41) edge node {0,R} (q40)
185
186 (q40) edge [bend right] node {2,R} (q60)
187 (q40) edge node {1,R} (q50)
188 (q41) edge [bend right] node {2,R} (q61)
189 (q41) edge node {1,R} (q51)
190 (q42) edge [bend right] node {2,R} (q62)
191 (q42) edge node {1,R} (q52)
192
193 (q50) edge [loop below] node {$\begin{array}{c}1,R\\0,R\end{array}$} (q50)
194 (q51) edge [loop below] node {$\begin{array}{c}1,R\\0,R\end{array}$} (q51)
195 (q52) edge [loop below] node {$\begin{array}{c}1,R\\0,R\end{array}$} (q52)
196 (q50) edge [bend left,looseness=2] node {2,R} (q60)
197 (q51) edge [bend left,looseness=2] node {2,R} (q61)
198 (q52) edge [bend left,looseness=2] node {2,R} (q62)
199
200 (q60) edge node {0,R} (q61)
201 (q61) edge node {0,R} (q62)
202 (q62) edge node {0,R} (q63)
203 (q63) edge node {4,R} (q53)
204 ;
205\end{tikzpicture}
206\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.}
207\label{fig:2dfa}
208\end{figure}
209
210Om te laten zien dat een \DFA minstens $n^n$ toestanden nodig heeft moet je
211gebruik maken van het feit dan een \DFA niet terug kan lopen. Het zal dus een
212`geheugen' moeten maken om het maximale $0$ woord voor de `splitsing' ($2^k$)
213te kunnen onthouden om zo te kijken of het overeen komt het $0$ woord na de
214`splitsing'. Omdat je voor elke $F_i$ waarbij $1 \ge i \ge n$ minimaal $n$
215toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
216bestaan, heb je dus minimaal $n^n$ toestanden nodig.
217
218Dit vertaald zich in een Myhill-Nerode relatie om het aantal toestanden te
219kunnen bepalen. $F_p$ en $F_q$ waarbij $p < q, 1 \le p,q \le n$ is
220onderscheidbaar, door voor $z=2*0*4$ te nemen, zodanig dat het woord door $F_q$
221geaccepteerd wordt, maar niet door $F_p$, door $|z|_2 \ge p$ te kiezen.
222
223Voor elke $F_i : 1 \ge i \ge n$ geldt dat deze `intern' ook $i^2$ unique
224toestanden geeft. We splitsen de woorden bij $2$, zodat we over een `prefix' en
225`suffix' kunnen praten. Een `prefix' past maar bij "{e}"{e}n `suffix'. De
226`suffixes' die gegenereeerd worden van de vorm $2*0*4$, kan $i^2$ vormen
227aannemen (bijvoorbeeld $i=2 {204,2004,22004,2204}$).
228Deze unique suffixes zorgen ervoor dat de Myhill-Nerode toepassing een
229substring $z$ kan vinden welke een van de unique suffixes bevat, waardoor het
230`prefix' niet samenkomt met een `suffix'.
231
232\section{Opgave 3.47}
233
234Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' $\Rightarrow$ `de klasse van
235talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) $\Rightarrow$ (a)]
236aan de hand van het volgende voorbeeld:
237Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q =
238\{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden
239die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die
240hoger dan $k$ genummerd zijn.
241
242
243$R_{i,j,k}$ accepteert als $q_i \in q_1, q_j \in F$.
244Om $R_{i,j,k+1}$ te verkrijgen, nemen we eerst de toestanden van $R_{i,j,k}$,
245deze verenigen we dan met alle toestanden die we vanuit $R_{i,j,k}$ kunnen
246bereiken met een transities $\delta(a,k+1) : i \le a \le j$, die in een
247\underline{nieuwe} toestand uitkomen, de lussen hebben geen meerwaarde voor ons
248doel. De begin toestand is te markeren als $R_{i,j,0} = {q_1} : i = j = 1$.
249
250\section{Opgave 3.54}
251
252Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en definieer:
253\begin{equation}
254L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\}
255\end{equation}
256Dit zijn dus de woorden waarbij alle elementen precies \'{e}\'{e}n keer in voor
257komen. Bijvoorbeeld $L_3 = \{123,132,213,231,312,321\}$.
258
259Om te laten zijn dat er minimal een reguliere expressie van lengte $2^{n-1}$
260nodig is om $L_n$ te specificeren, moet de \emph{Myhill-Nerode} stelling
261toegepast worden. Vanwege de eigenschap dat prefix uniek is, zat het nooit
262mogelijk worden om aan beiden woorden hetzelfde toe te voegen zodanig dat ze in
263elkaars klasse terecht komen. (elk `bit' informatie is relevant). Voor alle
264klasse zal dus apart gekeken worden of aan de eisen voldaan wordt. Om dus alle
265getallen $n$ van de string te controleren of zij uniek is zijn minimaal
266$2^{n-1}$ toestanden nodig.
267
268Echter voor $\overline{L_n}$ is wel een reguliere expressie te vinden en wel
269in de grootte $O(n^2)$. Door simpelweg voor elke $i \in \Sigma^*$ een reguliere
270expressie te maken van de vorm $x^*~i~x^*~i~x^*$ waarbij $x = Sigma^* - i$.
271
272\section{Opgave 3.68}
273
274Voor een woord $w \in \Sigma^*$, is een palc($w$) de korte palindroom $x$
275zodanig dat $w$ een prefix is van $x$. en palc($L$) = $\bigcup_{w \in L}\{palc(w)\}$.
276
277Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$
278waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$
279is, moet er gebruik gemaakt worden van een tegenstelling. Als $w$ nog een
280palindroom aan het einde zal bevatten $uu$, dan ziet $x$ er als volgt uit
281$wuuuuw$, dit is niet de korte palindroom ($ww$), welke $uuuu$ er nog makkelijk
282uit weggehaald had kunnen worden. Een willekeurige suffix van $w$ kan ook geen
283palindroom vormen die nog `weggesneden' kan worden, omdat hij anders al in den
284beginne een palindroom had moeten zijn.
285
286Als $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke
287`vertaling' van een woord $w$ naar zijn palc($w$). De nieuwe woorden zullen in
288het slechtste geval evenveel blijven, maar de taal kan ook kleiner worden.
289
290De andere kant op geldt dit \underline{niet}, als $L$ regulier is, dan is het
291onbeslist of palc\textsuperscript{-1}($L$) ook regulier is. Het kan namelijk
292zeer goed dat een (ingewikkelde) functie die woorden genereerde welke een
293palindroom zijn en die aan een vast prefix ($p$) toegevoegd. De \emph{palc}
294functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is.
295
296
297\section{Opgave 3.69}
298
299Laat $x_1,x_2,\ldots,x_k \in \Sigma^*$. Om te laten zien dat $\Sigma^* -
300x_{1}^{*}x_{2}^{*} \cdots x_{k}^*$ eindig is dan en slechts als $|\Sigma| = 1$
301en gcd($|x_1|,|x_2|,\ldots,|x_k|$) = 1 moet er een paar dingen bewezen worden
302a) aantonen dat het \underline{niet} geldt voor de tegenvoorbeelden a) $gcd
303> 1$ b) $|\Sigma| > 1$ en tevens moet aangetoond worden waarom de eindigheid
304 voor dit specifieke geval geldt.
305
306Merk op dat met een gcd van 1 alle getallen in de verzameling \{1,
307priemgetallen\} zitten. Bij een alfabet van 1 letter hoeft er enkel maar
308gesproken worden over lengtes. Standaard zitten alle lengtes in de taal.
309Aangezien de `deel-lengtes' ($x_1,x_2,\ldots,x_k$) nul of meer keer in de
310verzameling in de verzameling mogen zitten. Zal je uiteindelijk overblijven met
311een eindige set lengtes. In het geval dat er lengte 1 gevonden wordt, zal zelfs
312de lege set het antwoord zijn.
313
314a) Als $|\Sigma| > 1$, bijvoorbeeld $\{1,2\}$ dan kan er een oneindige
315verzameling gemaakt worden, door $x_1,x_2,\ldots,x_k \in 1^*$. De $2*$ zal dan een
316oneindige verzameling vormen.
317
318b) $gcd > 1$, bijvoorbeeld $2$ dan kan er een oneindige verzameling gemaakt
319worden, doordat niet alle woorden gemaakt kunnen worden. Enkel worden van
320`even' lengte in dit geval. Waardoor de `oneven' woorden een eindige string
321gaan vormen. Bij grotere waardes ($r$) kunnen ook 'groepen' (de $|r|* - 1$)
322bijvoorbeeld niet meer bereikt worden, welke dan tot een oneindige verzameling
323kunnen groeien.
324
325\begin{thebibliography}{1}
326\bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
327languages and automata theory }, \emph{Cambridge University Press}, 2009.
328\end{thebibliography}
329\newpage
330\end{document}
Note: See TracBrowser for help on using the repository browser.