Changeset 250 for liacs/TPFL2010/assignment1/report.tex
- Timestamp:
- Dec 10, 2010, 11:02:26 PM (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
liacs/TPFL2010/assignment1/report.tex
r249 r250 277 277 zodanig dat $w$ een prefix is van $x$. en palc($L$) = $\bigcup_{w \in L}\{palc(w)\}$. 278 278 279 Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$279 a) Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$ 280 280 waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$ 281 is, moet er gebruik gemaakt worden van een tegenstelling. Als $w$ nog een 282 palindroom aan het einde zal bevatten $uu$, dan ziet $x$ er als volgt uit 283 $wuuuuw$, dit is niet de korte palindroom ($ww$), welke $uuuu$ er nog makkelijk 284 uit weggehaald had kunnen worden. Een willekeurige suffix van $w$ kan ook geen 285 palindroom vormen die nog `weggesneden' kan worden, omdat hij anders al in den 286 beginne een palindroom had moeten zijn. 287 288 Als $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke 289 `vertaling' van een woord $w$ naar zijn palc($w$). De nieuwe woorden zullen in 290 het slechtste geval evenveel blijven, maar de taal kan ook kleiner worden. 291 292 De andere kant op geldt dit \underline{niet}, als $L$ regulier is, dan is het 293 onbeslist of palc\textsuperscript{-1}($L$) ook regulier is. Het kan namelijk 294 zeer goed dat een (ingewikkelde) functie die woorden genereerde welke een 295 palindroom zijn en die aan een vast prefix ($p$) toegevoegd. De \emph{palc} 296 functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is. 297 281 is, moet er gebruik gemaakt worden van een tegenstelling. Neem aan dat $w$ een 282 palindroom aan het einde zal bevatten $uu$ en dus van de vorm is $ruu$ dan ziet 283 palc($w$) er als volgt uit $ruuuur$, dit is niet de korte palindroom 284 ($rr$), welke $uuuu$ er nog uit $x$ weggehaald had kunnen worden. 285 Een willekeurige suffix van $w$ kan dus geen palindroom vormen die nog 286 `weggesneden' kan worden, omdat hij anders al in den beginne een palindroom had 287 moeten zijn. 288 $t$ moet wel de \underline{langste} palindroom suffix van $w$ zijn, omdat 289 anders een `dubbele' palindroom problemen op gaat leveren. Neem bijvoorbeeld 290 $w$ van de vorm is $ruuyy$ als je van de palindroom $yy$ verwijderd, zal 291 palc($w$) = $ruuuur$. Dit is niet de kortste palindroom ($rr$). 292 293 b) Neem $L = \{ uvxyz : u,x,z \in 1^*~en~v,u \in 0^* \}$ en $\Sigma = \{0,1\}$. 294 De woorden die palc($L$) moeten bevatten zijn alle woorden van $L$ minus de 295 woorden $|x|_1 = even, |v|_0 = |y|_0, |u|_0 = |z|_0$. Die set komt niet door 296 het pumping lemma en is dus palc($L$) is \underline{niet} regulier. 297 298 c) Neem palc\textsuperscript{-1}($L$), dan is dit $\{ x \in L, u \in \Sigma^* : 299 xuu \}$, welke alle woorden zijn met hun prefix in $L$ en hun suffix is een 300 palindroom. Het genereren van palindromen met een reguliere taal is 301 \underline{niet} mogelijk, dus palc\textsuperscript{-1}($L$) is 302 \underline{niet} regulier. 298 303 299 304 \section{Opgave 3.69} … … 301 306 Laat $x_1,x_2,\ldots,x_k \in \Sigma^*$. Om te laten zien dat $\Sigma^* - 302 307 x_{1}^{*}x_{2}^{*} \cdots x_{k}^*$ eindig is dan en slechts als $|\Sigma| = 1$ 303 en gcd($|x_1|,|x_2|,\ldots,|x_k|$) = 1 moet er een paar dingen bewezen worden 304 a) aantonen dat het \underline{niet} geldt voor de tegenvoorbeelden a) $gcd 305 > 1$ b) $|\Sigma| > 1$ en tevens moet aangetoond worden waarom de eindigheid 306 voor dit specifieke geval geldt. 307 308 Merk op dat met een gcd van 1 alle getallen in de verzameling \{1, 309 priemgetallen\} zitten. Bij een alfabet van 1 letter hoeft er enkel maar 310 gesproken worden over lengtes. Standaard zitten alle lengtes in de taal. 311 Aangezien de `deel-lengtes' ($x_1,x_2,\ldots,x_k$) nul of meer keer in de 312 verzameling in de verzameling mogen zitten. Zal je uiteindelijk overblijven met 313 een eindige set lengtes. In het geval dat er lengte 1 gevonden wordt, zal zelfs 314 de lege set het antwoord zijn. 315 316 a) Als $|\Sigma| > 1$, bijvoorbeeld $\{1,2\}$ dan kan er een oneindige 317 verzameling gemaakt worden, door $x_1,x_2,\ldots,x_k \in 1^*$. De $2*$ zal dan een 318 oneindige verzameling vormen. 319 320 b) $gcd > 1$, bijvoorbeeld $2$ dan kan er een oneindige verzameling gemaakt 321 worden, doordat niet alle woorden gemaakt kunnen worden. Enkel worden van 322 `even' lengte in dit geval. Waardoor de `oneven' woorden een eindige string 323 gaan vormen. Bij grotere waardes ($r$) kunnen ook 'groepen' (de $|r|* - 1$) 324 bijvoorbeeld niet meer bereikt worden, welke dan tot een oneindige verzameling 325 kunnen groeien. 308 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. 309 310 311 $\Rightarrow$: Door middel van een tegenstelling kunnen we bewijzen dat 312 $|\Sigma| = 1$ moet zijn. Neem $|\Sigma| > 1$ en $x_1,x_2,\ldots,x_n = 0$ dan 313 is deze oneindig, en wel in de vorm $(\Sigma \backslash {0})^*$. Door een 314 tweede tegenstelling tonen we aan dat de gcd \'{e}\'{e}n moet zijn. Als $|\Sigma| 315 = 1$ en $g$ = gcd($|x_1|,|x_2|,\ldots,|x_n|$) $\neq$ 1 dan komen er enkel woorden 316 voor van lengte $g^n : n = 1 .. n$ Hierdoor zullen de woorden met lengte 317 $(g-1)^*$ een oneindige reeks vormen. 318 319 $\Leftarrow$: Doordat $|\Sigma| = 1$ is de lengte van de string indentiek aan 320 zijn formaat. Met een gcd($|x_1|,|x_2|,\ldots,|x_n|$) $\neq$ 1 kunnen we alle 321 bijna alle lengtes genereren door de eigenschap dat de nummers (relatief) priem 322 zijn.\footnote{Dit is een grote gok, aangenomen dat er een Stelling bestaat, 323 welke stelt dat je uit 2 priemgetallen vanaf een bepaald punt alle getallen kan 324 genereren.} 326 325 327 326 \begin{thebibliography}{1}
Note:
See TracChangeset
for help on using the changeset viewer.