Changeset 239 for liacs/TPFL2010/assignment2

Timestamp:

Nov 26, 2010, 10:59:13 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Ready for delivery

Location:

liacs/TPFL2010/assignment2

Files:

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

liacs/TPFL2010/assignment2/report.tex

@@ -40 +40 @@
 Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
 \cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
-(9, 18, 24, 26, 32, 35, 41) van hoofdstuk 4 behandeld worden. De opgaven zijn
+(9, 18, 24, 26, 32, 37, 41) van hoofdstuk 4 behandeld worden. De opgaven zijn
 willekeurig gekozen met behulp van een kans generator, het kan dus zijn dat
 niet alle onderwerpen van hoofdstuk 4 behandeld worden.
@@ -99 +99 @@
 
 
-\section{Opgave 4.35}
+\section{Opgave 4.37}
+perm($x$) is de set van alle permutaties van de letters van $x$. Voor talen is
+perm($L$) := $\bigcup_{x\in L}$ perm($x$). perm($L$) is niet context-vrij als
+$L$ de reguliere taal is \{$x \in a^*b^*c^*$ : $|x|_a,|x|_b,|x|_c$ even zijn\}.
 
+[Dit is handen wapperen, ik zou graag wel willen weten hoe dit bewezen
+kan worden] Als $L$ echter een reguliere taal over een alfabet van twee
+symbolen is, dan zal perm($L$) context-vrij zijn. Welke de reguliere taal,
+maximaal \'e\'en complexe relatie kan aangaan en wel namelijk tussen de twee
+symbolen in.  Alle andere gevallen (enkel relatie \'e\'en symbool) is er maar
+een enkelvoudige afhankelijk gecodeerd. Pak bijvoorbeeld de ingewikkende 
+\{$x \in a^*b^*$ : $|x|_a,|x|_b$ even zijn\}. De permutatie van bijvoorbeeld
+$aabb$ zullen zijn ${aabb,abba,abab,baba,baab,bbaa}$, waarbij in het
+context-vrije domain een analoge taal ontstaan, waarbij het aantal a `even'
+moet zijn om te accepteren en het aantal b gelijk aan het aantal `a'.
 
 \section{Opgave 4.41}
-
+Om te bewijzen dat, de taal van alle woorden over de $\{0,1\}$ welke geen
+prefixen zijn van een Thue-Morse woord context-vrij is, moet er gekeken worden
+naar het meer generieke geval. Thue-Morse woorden zijn overlap-vrij, een
+context-vrije taal alle woorden opsomt welke een overlap bevatten is dus
+voldoende. Woorden met een overlap bevatten de serie $cxcxc$ waarbij $c$ een
+letter is en $x$ een woord, de overlap is dan $cxc$. De taal van de woorden
+ziet er dus als volgt uit: $\{0,1\}^*1x1x\{0,1\}^*$ of $\{0,1\}^*0x0x\{0,1\}^*$
+waarbij $x := \{0,1\}\{0,1\}^*$. Beiden delen zijn met een (niet
+determistische) gramatica te maken, door expansitie te doen vanuit `het
+midden'. Waarbij te denken is aan een soortgelijke setup (a,b ipv 0,1):
+\begin{verbatim}
+S -> JMJ
+J -> aJ|bJ|a|b
+M -> aOa|bPb
+O -> aOa|bOb|a
+P -> aPa|bPb|b
+\end{verbatim}