Changeset 261 for liacs/TPFL2010/assignment2

Timestamp:

Dec 19, 2010, 11:16:55 PM (14 years ago)

Author:

Rick van der Zwet

Message:

To-be handed in.

Location:

liacs/TPFL2010/assignment2

Files:

• report.pdf (modified) ( previous)
• report.tex (modified) (5 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, 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.
+(9, 18, 24, 26, 32, 37, 41) van hoofdstuk 4 behandeld worden.
 \end{abstract}
 
 \section{Opgave 4.9}
 Laat $L \subseteq \all$ de taal zijn en defineer $\sigma(L) = \{x \in \all : xy
-\in voor~alle~y \in \all\}$. Als $L$ context-vrij is $\sigma(L)$ ook
-context-vrij. Omdat $y = \all$ is dit een reguliere taal. $xy$ zal dan een
-context-vrije taal zijn (gesloten onder concatenatie). $xy \in L$ is vereniging
-van $xy$ met $L$, welke onder context-vrije talen gesloten is. Hierdoor zal
-$\sigma(L)$ (een subset) ook weer context-vrij zijn.
+\in L~voor~alle~y \in \all\}$. Als $L$ context-vrij is dan is $\sigma(L)$ ook
+context-vrij. Als naar de taal $L$ gekeken wordt moet de taal uit twee delen
+($A \cdot B$) opgebouwd zijn wil $xy \in L$ accepteren. $A$ zal $x$
+beschrijven. $B$ moet een reguliere taal zijn van de vorm $\all$. 
+
+Een $CFL$ waarbij het $RL$ suffix afgehaald wordt zal wederom een $CFL$ zijn
+(zie Opgave 4.18) en daarom is $\sigma(L)$ ook weer context-vrij.
 
 
 \section{Opgave 4.18}
-Als $L$ een context-vrije taal is en $R$ een reguliere taal dan de rechter
-quotiënt $L/R = \{x \in \all: \exists y \in R~zodat~xy \in L \}$ is ook een
-context-vrije taal. $xy$ zijn de woorden in $L$ waarbij geldt dat de suffix
-$y$ regulier is. Stel dat $x$ geen context-vrije taal was. Dan zou $xy$ ook
-geen context-vrije taal zijn. Wat niet kan welke $L$ context-vrij is en in die
-hoedanigheid ook de subsets van $L$.
+Als $L$ een context-vrije taal is en $R$ een reguliere taal dan is de rechter
+quoti"{e}nt $L/R = \{x \in \all: \exists y \in R~zodat~xy \in L \}$  ook een
+context-vrije taal. $xy$ zijn dus de woorden in $L$ waarbij geldt dat het
+`staartje' $y$ wat eraf gehaald wordt in de reguliere taal $R$ zit. 
+
+Om dit te bewijzen gaan we naar de $PDA$ van $L$ kijken. Hierbij kan $R$ in de
+omgekeerde volgorde door de taal gehaald worden om zo de eindtoestand naar
+`voren' te halen. Dit levert een kortere $PDA$ op.
+
 
 \section{Opgave 4.24}
-Als $s^{[-1]}(L) := \{x : s(x) \cap L \neq \emptyset\}$ en $s$ verbind letters
+Als $s^{[-1]}(L) := \{x : s(x) \cap L \neq \emptyset\}$ en $s$ verbindt letters
 met reguliere talen en $L$ is context-vrij. Dan is $s^{[-1]}(L)$ niet altijd
-CFL, L een een verzameling kan zijn van alle talen van de letters waarbij geldt
-dat de lengte van de letters even moet zijn, welke geen context-vrije
-verzameling is.
+CFL. $s^{[-1]}(L)$ kan een verzameling kan zijn van de talen waarbij de lengte
+van de letters even moet zijn, welke geen context-vrije verzameling is.
 
 Hetzelfde probleem doet voor als $s$ letters aan context-vrije talen verbindt.
@@ -80 +82 @@
 symbool eraf haalt en de tweede de gewenste symbolen er weer op zet.
 
-De bovengenoemde methode zorgt voor maar \'e\'en mogelijk pad. Er zal de de
+De bovengenoemde methode zorgt voor maar \'e\'en mogelijk pad. Het zal de
 DPDA structuur (indien present) dus niet aantasten.
 
@@ -100 +102 @@
 
 \section{Opgave 4.37}
-perm($x$) is de set van alle permutaties van de letters van $x$. Voor talen is
+a) 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\}.
+$L$ de reguliere taal is \{$x \in a^*b^*c^*$ : $|x|_a,|x|_b,|x|_c$ is even \},
+omdat dit onder andere $\{ a^{n}b^{n}c^{n} : n = 2*i, i \ge 0 \}$ bevat, welke
+niet context-vrij~\cite{JS2009}[pg.~108] is.
 
-[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
+b) 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
@@ -115 +118 @@
 moet zijn om te accepteren en het aantal b gelijk aan het aantal `a'.
 
+\newpage
 \section{Opgave 4.41}
+\begin{figure}
+\center
+\begin{tikzpicture}
+  \node[place,pin={[pin edge={style=<-,black,thick}]left:}] (q0) {0};
+  \node[place] (q1) [right=of q0] {1};
+\path[->]
+  (q0) edge [loop above] node[above] {0} (q0)
+  (q1) edge [loop above] node[above] {0} (q1)
+  (q0) edge [bend left] node[above] {1} (q1)
+  (q1) edge [bend left] node[below] {1} (q0)
+
+  ;
+\end{tikzpicture}
+\caption{Automaton generating the Thue-Morse sequence as the sequence generated
+by the following DFA, where one inputs n expressed in base 2}
+\label{fig:tm}
+\end{figure}
 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
+prefixen zijn van een Thue-Morse woord context-vrij is. Thue-Morse woorden zijn
+overlap-vrij en kunnen door een automaat gegenereert worden, zie hiervoor
+Figuur~\ref{fig:tm}\footnote{\url{http://www.cs.uwaterloo.ca/~shallit/Talks/canad4.pdf}}.
+Een paar eigenschappen het Thue-Morse woord zijn het feit dat er geen overlap
+in voorkomt en ook geen `blokken' in de vorm van $XXX$ waarbij $X \in \all$.
+
+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
-deterministische) grammatica te maken, door expansie 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}
+waarbij $x := \{0,1\}\{0,1\}^*$. Dit is niet een context-vrije taal. Welke het
+\emph{pumping-lemma} hier faalt. Er moet dus gekeken worden naar een meer
+generiek geval. Dit kunnen we door verschillende talen te generen en gebruik te
+maken van het geven feit dat de klasse van de context-vrije-talen gesloten zijn
+onder een eindige verzameling. Deze talen zijn te vinden in
+\cite{BS2009}[pg.~89 Theorem 2.24].
 
 
@@ -138 +158 @@
 \bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
 languages and automata theory }, \emph{Cambridge University Press}, 2009.
-\end{thebibliography}
+\bibitem[BS2009]{BS2009}J. Berstel, \emph{Combinatorics on words: Christoffel
+words and repetitions in words}, \emph{American Mathematical Society}, 2009.
+ \end{thebibliography}
 \newpage
 \end{document}