Changeset 250 for liacs/TPFL2010/assignment1

Timestamp:

Dec 10, 2010, 11:02:26 PM (14 years ago)

Author:

Rick van der Zwet

Message:

To be delivered.

Location:

liacs/TPFL2010/assignment1

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (2 diffs)

liacs/TPFL2010/assignment1/report.tex

@@ -277 +277 @@
 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$
+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. 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.
-
+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}
@@ -301 +306 @@
 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. 
+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}