% % $Id: report.tex 571 2008-04-20 17:31:04Z rick $ % \documentclass[12pt,a4paper]{article} \frenchspacing \usepackage[english,dutch]{babel} \selectlanguage{dutch} \usepackage[pdftex]{graphicx} \usepackage{url} \usepackage{amssymb,amsmath} \usepackage{float} \usepackage{tikz} \usepackage{fixltx2e} \usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri} \setlength\parindent{0pt} \setlength\parskip{\baselineskip} \floatstyle{ruled} \newfloat{algoritm}{thp}{lop} \floatname{algoritm}{Algoritme} \title{Opdracht 2 \\ \large{Topics on Parsing and Formal Languages - fall 2010}} \author{Rick van der Zwet\\ \texttt{}} \date{\today} \begin{document} \newcommand{\DFA}{\emph{DFA}~} \newcommand{\qed}{\hfill \ensuremath{\Box}} \newcommand{\all}{\Sigma^*} \maketitle \begin{abstract} 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. \end{abstract} \section{Opgave 4.9} Laat $L \subseteq \all$ de taal zijn en defineer $\sigma(L) = \{x \in \all : xy \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 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$ verbindt letters met reguliere talen en $L$ is context-vrij. Dan is $s^{[-1]}(L)$ niet altijd 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. \section{Opgave 4.26} Gegeven een PDA $M$ kan je altijd een $M^{'}$ maken welke de eigenschap heeft dat geen enkele stap het huidige symbool op de stapel vervangt (geen transities van de vorm $(p,\gamma Y) \in \delta(q,a,X)~waarbij~X \neq Y$). Dus dat alle stappen, of een symbool van de stapel afhalen, of een string van symbolen op de stapel zetten. Dit is te doen door de huidige substitutie' transities te vervangen door een tweetal (gekoppelde) transities. Waarbij de eerste het symbool eraf haalt en de tweede de gewenste symbolen er weer op zet. De bovengenoemde methode zorgt voor maar \'e\'en mogelijk pad. Het zal de DPDA structuur (indien present) dus niet aantasten. \section{Opgave 4.32} Als $\psi$ een Parikh map is, dan zijn er lange Engelse woorden over een bepaald alfabet voor specifieke eigenschappen. Voorbeelden zijn te vinden in de onderstaande tabel. \begin{tabular}{l | l | l } eigenschap & woorden & alfabet \\ \hline \hline $\psi(w)$ alle items gelijk aan 1 & dutchwomen & $\{d,u,t,c,h,w,o,m,e,n\}$\\ $\psi(w)$ alle items gelijk aan 2 & tomtom & $\{t,o,m\}$\\ $\psi(w)$ alle items gelijk aan 3 & sestettes & $\{s,e,t\}$\\ $\psi(w)$ alle items $\ge$ 2 & unprosperousness & $\{e,n,o,p,r,s,u\}$\\ $\psi(w)$ $(1,2,2,3,3,3)$ & chincherinchee & $\{r,i,n,c,h,e\}$\\ \end{tabular} \section{Opgave 4.37} 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$ 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. 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 symbolen in. Alle andere gevallen (enkel relatie \'e\'en symbool) is er maar een enkelvoudige afhankelijk gecodeerd. Pak bijvoorbeeld de ingewikkelde \{$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 domein een analoge taal ontstaan, waarbij het aantal a `even' 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. 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\}^*$. 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]. \begin{thebibliography}{1} \bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal languages and automata theory }, \emph{Cambridge University Press}, 2009. \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}