[2] | 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}
|
---|
[224] | 10 | \usepackage[pdftex]{graphicx}
|
---|
[2] | 11 | \usepackage{url}
|
---|
| 12 | \usepackage{amssymb,amsmath}
|
---|
[224] | 13 | \usepackage{float}
|
---|
[226] | 14 | \usepackage{tikz}
|
---|
[227] | 15 | \usepackage{fixltx2e}
|
---|
[2] | 16 |
|
---|
[226] | 17 | \usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}
|
---|
| 18 |
|
---|
| 19 |
|
---|
| 20 |
|
---|
| 21 | \setlength\parindent{0pt}
|
---|
| 22 | \setlength\parskip{\baselineskip}
|
---|
[224] | 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}}
|
---|
[2] | 29 | \author{Rick van der Zwet\\
|
---|
[224] | 30 | \texttt{<hvdzwet@liacs.nl>}}
|
---|
[2] | 31 | \date{\today}
|
---|
| 32 |
|
---|
[224] | 33 |
|
---|
[2] | 34 | \begin{document}
|
---|
[224] | 35 | \newcommand{\DFA}{\emph{DFA}~}
|
---|
| 36 | \newcommand{\qed}{\hfill \ensuremath{\Box}}
|
---|
[2] | 37 | \maketitle
|
---|
[224] | 38 | \begin{abstract}
|
---|
| 39 | Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
|
---|
| 40 | \cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
|
---|
[243] | 41 | (3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden.
|
---|
[224] | 42 | \end{abstract}
|
---|
[2] | 43 |
|
---|
[224] | 44 | \section{Opgave 3.3}
|
---|
| 45 | Als $L \subseteq \Sigma^*$ is regulier dan is de taal
|
---|
| 46 | \begin{equation}
|
---|
| 47 | 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
|
---|
| 48 | \end{equation}
|
---|
| 49 | regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
|
---|
[229] | 50 | modelleren 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$
|
---|
[224] | 52 | die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
|
---|
[229] | 53 | en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeld.
|
---|
[224] | 54 | $voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
|
---|
[229] | 55 | maar maak aanpassingen zodanig dat de nieuwe toestanden ook gelezen worden. Dus
|
---|
[224] | 56 | $\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$
|
---|
[243] | 57 | is gelijkt aan de oude acceptatie toestand.
|
---|
[226] | 58 | \\
|
---|
[229] | 59 | De nieuwe \DFA $P$ beschrijft $2L$ en dus is $2L$ regulier.
|
---|
[224] | 60 | \qed
|
---|
| 61 |
|
---|
| 62 |
|
---|
[225] | 63 | \section{Opgave 3.20}
|
---|
[243] | 64 | Laat $\Sigma = \{0,1\}$ zijn. Een voorbeeld van de taal $L \subseteq
|
---|
[225] | 65 | \Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
|
---|
[229] | 66 | gelijkheid relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
|
---|
[244] | 67 | eigen equivalentie klasse is. Dit wilt zeggen dat $xR_{l}y$ dan en slechts dan
|
---|
| 68 | voor alle $z \in \Sigma^*$, is er een $xz \in L$ dan en slechts als $yz \in L$.
|
---|
| 69 | Omdat hier gezocht wordt naar een taal waarbij de woorden allemaal equivalentie
|
---|
| 70 | klassen op-zich zijn, zal alle elementen met elkaar vergeleken kunnen worden
|
---|
| 71 | door middel van $R_L$ en hier mogen geen positieve 'gevallen' uitkomen.
|
---|
[224] | 72 |
|
---|
[244] | 73 | De (triviale) taal $L = {01,10}$ is een voorbeeld hiervan. Beiden woorden hebben
|
---|
| 74 | hun eigen klasse. Als $x = 0$ en $y = 1$, bestaat er een $z = 1$, zodanig dat
|
---|
| 75 | $xz \in L, yz \notin L$.
|
---|
[226] | 76 |
|
---|
[245] | 77 | De taal $M = \{{0}^* : |M|_0~is~een~priemgetal\}$ is een ander voorbeeld. Als we
|
---|
[244] | 78 | kijken naar $aR_{l}b$ kan er altijd een $z$ gevormd worden zodanig dat $az \in
|
---|
| 79 | M, bz \notin M$. Bijvoorbeeld $a = 0^3, b =0^5, z = 0^4$. Deze eigenschap wordt
|
---|
| 80 | afgedwongen door het `feit' dat er geen relatie bestaat tussen de lengtes
|
---|
| 81 | tussen opeenvolgende priemgetallen.\footnote{Ik heb dit voor gemak aangenomen,
|
---|
| 82 | de praktijk is echter dat is nog een groot wiskundig vraagstuk is.}
|
---|
[226] | 83 |
|
---|
[244] | 84 |
|
---|
| 85 | \section{Opgave 3.22*}
|
---|
[229] | 86 | Om aan te tonen dat een \emph{2DFA} exponentieel meer expressief is dan een
|
---|
[226] | 87 | \DFA voor bepaalde talen kijken we naar de volgende taal; Laat $n$ een integer
|
---|
[229] | 88 | $\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefinieerd:
|
---|
[226] | 89 | \begin{equation}
|
---|
[244] | 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\}
|
---|
[226] | 91 | \end{equation}
|
---|
| 92 |
|
---|
| 93 | Als eerste kan de $F_n$ door een \emph{2DFA} van $O(n)$ toestanden geaccepteerd
|
---|
| 94 | worden, welke aan te tonen is door eerst te kijken naar de eigenschappen van
|
---|
[245] | 95 | $F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i_k$ zowel voor als na
|
---|
[226] | 96 | de $2^k$ moet voorkomen. Waarbij $2^k$ aangeeft, waar deze $0$-reeks gevonden
|
---|
[245] | 97 | kan worden bij de plek $k$. De \emph{2DFA} moet dus twee dingen doen. Het
|
---|
[226] | 98 | aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de
|
---|
[245] | 99 | tweede plek variabele wordt gedefinieerd. De aanpak kan als volgt gezien worden:
|
---|
| 100 | \begin{verbatim}
|
---|
[246] | 101 | 1. controleren of |1| <= 2de 0-reeks dmv 'knopen-strook' (knopen 0.X en 1.X).
|
---|
| 102 | 2. |2| tellen onthouden dmv 'knopen-strook' (knopen 2.X).
|
---|
| 103 | 3. naar gewenste locatie lopen (knopen 3.X).
|
---|
| 104 | 4. |0| tellen onthouden dmv 'knopen-strook' (knopen 4.X).
|
---|
| 105 | 5. naar begin 2de 0-reeks lopen (knopen 5.X).
|
---|
| 106 | 6. 0-reeks vergelijken (knopen 6.X).
|
---|
[245] | 107 | \end{verbatim}
|
---|
[246] | 108 | Voor deze aanpak zijn 3 `knopen-stroken' nodig, 3 `transitie-lagen' en 1 controle
|
---|
| 109 | strook. In totaal dus in ongeveer $O(7n)$ knopen. Figuur~\ref{fig:2dfa} laat
|
---|
| 110 | de \emph{2DFA} zien.
|
---|
[226] | 111 |
|
---|
| 112 |
|
---|
| 113 | \begin{figure}
|
---|
| 114 | \center
|
---|
[246] | 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 |
|
---|
[226] | 147 | \path[->]
|
---|
[245] | 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 |
|
---|
[246] | 169 | (q20) edge node {0,L} (q30)
|
---|
| 170 | (q21) edge node {0,L} (q31)
|
---|
| 171 | (q22) edge node {0,L} (q32)
|
---|
[245] | 172 |
|
---|
[246] | 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)
|
---|
[226] | 204 | ;
|
---|
| 205 | \end{tikzpicture}
|
---|
[246] | 206 | \caption{Opdracht 2.22a uitgewerkt voor $1 \le n \le 3$, niet geldige stappen zijn niet genoemd en moet allen naar een 'trap' knoop gestuurd worden. Uitbreiden dmv expanderen van `traviale' knopen.}
|
---|
[245] | 207 | \label{fig:2dfa}
|
---|
[226] | 208 | \end{figure}
|
---|
| 209 |
|
---|
| 210 | Om te laten zien dat een \DFA minstens $n^n$ toestanden nodig heeft moet je
|
---|
| 211 | gebruik 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$)
|
---|
| 213 | te 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$
|
---|
| 215 | toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
|
---|
| 216 | bestaan, heb je dus minimaal $n^n$ toestanden nodig.
|
---|
| 217 |
|
---|
[227] | 218 | \section{Opgave 3.47}
|
---|
[226] | 219 |
|
---|
[227] | 220 | Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' => `de klasse van
|
---|
| 221 | talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) => (a)]
|
---|
| 222 | aan de hand van het volgende voorbeeld:
|
---|
| 223 | Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q =
|
---|
[229] | 224 | \{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden
|
---|
[227] | 225 | die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die
|
---|
| 226 | hoger als $k$ genummerd zijn.
|
---|
[226] | 227 |
|
---|
[229] | 228 | Om dit te doen is een recursieve formule nodig, welke $R_{i,j,k}$ als invoer
|
---|
[227] | 229 | heeft. a) Kijk welke transities er mogelijk zijn in $\delta$ met toestand $i$ als
|
---|
| 230 | begin positie. Plaats deze op de `stapel'. b) Werk de elementen op de stapel
|
---|
| 231 | stuk voor stuk af volgens dezelfde methodiek. Stop pas als de $\delta$
|
---|
| 232 | resultaat $j$ bevat. Let erop dat oneindige herhalingen gedetecteerd moeten
|
---|
| 233 | worden om het algoritme te laten termineren. Je kan het zien als het volledig
|
---|
| 234 | doorzoeken van een boom met in de wortel de knoop $i$.
|
---|
[226] | 235 |
|
---|
[224] | 236 | \section{Opgave 3.54}
|
---|
[227] | 237 |
|
---|
[229] | 238 | Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en definieer:
|
---|
[227] | 239 | \begin{equation}
|
---|
| 240 | L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\}
|
---|
| 241 | \end{equation}
|
---|
| 242 | Dit zijn dus de woorden waarbij alle elementen precies \'{e}\'{e}n keer in voor
|
---|
| 243 | komen. Bijvoorbeeld $L_3 = \{123,132,213,231,312,321\}$.
|
---|
| 244 |
|
---|
| 245 | Om te laten zijn dat er minimal een reguliere expressie van lengte $2^{n-1}$
|
---|
| 246 | nodig is om $L_n$ te specificeren, moet de \emph{Myhill-Nerode} stelling
|
---|
| 247 | toegepast worden. Vanwege de eigenschap dat prefix uniek is, zat het nooit
|
---|
| 248 | mogelijk worden om aan beiden woorden hetzelfde toe te voegen zodanig dat ze in
|
---|
| 249 | elkaars klasse terecht komen. (elk `bit' informatie is relevant). Voor alle
|
---|
| 250 | klasse zal dus apart gekeken worden of aan de eisen voldaan wordt. Om dus alle
|
---|
| 251 | getallen $n$ van de string te controleren of zij uniek is zijn minimaal
|
---|
| 252 | $2^{n-1}$ toestanden nodig.
|
---|
| 253 |
|
---|
| 254 | Echter voor $\overline{L_n}$ is wel een reguliere expressie te vinden en wel
|
---|
| 255 | in de grootte $O(n^2)$. Door simpelweg voor elke $i \in \Sigma^*$ een reguliere
|
---|
| 256 | expressie te maken van de vorm $x^*~i~x^*~i~x^*$ waarbij $x = Sigma^* - i$.
|
---|
| 257 |
|
---|
[224] | 258 | \section{Opgave 3.68}
|
---|
[227] | 259 |
|
---|
| 260 | Voor een woord $w \in \Sigma^*$, is een palc($w$) de korte palindroom $x$
|
---|
| 261 | zodanig dat $w$ een prefix is van $x$. en palc($L$) = $\bigcup_{w \in L}\{palc(w)\}$.
|
---|
| 262 |
|
---|
| 263 | Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$
|
---|
[229] | 264 | waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$
|
---|
[227] | 265 | is, moet er gebruik gemaakt worden van een tegenstelling. Als $w$ nog een
|
---|
| 266 | palindroom aan het einde zal bevatten $uu$, dan ziet $x$ er als volgt uit
|
---|
| 267 | $wuuuuw$, dit is niet de korte palindroom ($ww$), welke $uuuu$ er nog makkelijk
|
---|
[229] | 268 | uit weggehaald had kunnen worden. Een willekeurige suffix van $w$ kan ook geen
|
---|
[227] | 269 | palindroom vormen die nog `weggesneden' kan worden, omdat hij anders al in den
|
---|
| 270 | beginne een palindroom had moeten zijn.
|
---|
| 271 |
|
---|
[229] | 272 | Als $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke
|
---|
[227] | 273 | `vertaling' van een woord $w$ naar zijn palc($w$). De nieuwe woorden zullen in
|
---|
| 274 | het slechtste geval evenveel blijven, maar de taal kan ook kleiner worden.
|
---|
| 275 |
|
---|
| 276 | De andere kant op geldt dit \underline{niet}, als $L$ regulier is, dan is het
|
---|
| 277 | onbeslist of palc\textsuperscript{-1}($L$) ook regulier is. Het kan namelijk
|
---|
[229] | 278 | zeer goed dat een (ingewikkelde) functie die woorden genereerde welke een
|
---|
| 279 | palindroom zijn en die aan een vast prefix ($p$) toegevoegd. De \emph{palc}
|
---|
[227] | 280 | functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is.
|
---|
| 281 |
|
---|
| 282 |
|
---|
[224] | 283 | \section{Opgave 3.69}
|
---|
| 284 |
|
---|
[227] | 285 | Laat $x_1,x_2,\ldots,x_k \in \Sigma^*$. Om te laten zien dat $\Sigma^* -
|
---|
| 286 | x_{1}^{*}x_{2}^{*} \cdots x_{k}^*$ eindig is dan en slechts als $|\Sigma| = 1$
|
---|
| 287 | en gcd($|x_1|,|x_2|,\ldots,|x_k|$) = 1 moet er een paar dingen bewezen worden
|
---|
| 288 | a) aantonen dat het \underline{niet} geldt voor de tegenvoorbeelden a) $gcd
|
---|
| 289 | > 1$ b) $|\Sigma| > 1$ en tevens moet aangetoond worden waarom de eindigheid
|
---|
[228] | 290 | voor dit specifieke geval geldt.
|
---|
[227] | 291 |
|
---|
[228] | 292 | Merk op dat met een gcd van 1 alle getallen in de verzameling \{1,
|
---|
| 293 | priemgetallen\} zitten. Bij een alfabet van 1 letter hoeft er enkel maar
|
---|
| 294 | gesproken worden over lengtes. Standaard zitten alle lengtes in de taal.
|
---|
| 295 | Aangezien de `deel-lengtes' ($x_1,x_2,\ldots,x_k$) nul of meer keer in de
|
---|
| 296 | verzameling in de verzameling mogen zitten. Zal je uiteindelijk overblijven met
|
---|
| 297 | een eindige set lengtes. In het geval dat er lengte 1 gevonden wordt, zal zelfs
|
---|
| 298 | de lege set het antwoord zijn.
|
---|
| 299 |
|
---|
| 300 | a) Als $|\Sigma| > 1$, bijvoorbeeld $\{1,2\}$ dan kan er een oneindige
|
---|
| 301 | verzameling gemaakt worden, door $x_1,x_2,\ldots,x_k \in 1^*$. De $2*$ zal dan een
|
---|
| 302 | oneindige verzameling vormen.
|
---|
| 303 |
|
---|
| 304 | b) $gcd > 1$, bijvoorbeeld $2$ dan kan er een oneindige verzameling gemaakt
|
---|
| 305 | worden, doordat niet alle woorden gemaakt kunnen worden. Enkel worden van
|
---|
| 306 | `even' lengte in dit geval. Waardoor de `oneven' woorden een eindige string
|
---|
| 307 | gaan vormen. Bij grotere waardes ($r$) kunnen ook 'groepen' (de $|r|* - 1$)
|
---|
| 308 | bijvoorbeeld niet meer bereikt worden, welke dan tot een oneindige verzameling
|
---|
| 309 | kunnen groeien.
|
---|
| 310 |
|
---|
[224] | 311 | \begin{thebibliography}{1}
|
---|
| 312 | \bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
|
---|
| 313 | languages and automata theory }, \emph{Cambridge University Press}, 2009.
|
---|
[2] | 314 | \end{thebibliography}
|
---|
| 315 | \newpage
|
---|
| 316 | \end{document}
|
---|