source: liacs/TPFL2010/assignment2/report.tex@ 240

%
% $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{<hvdzwet@liacs.nl>}}
\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. De opgaven zijn
willekeurig gekozen met behulp van een kans generator, het kan dus zijn dat
niet alle onderwerpen 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.


\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$.

\section{Opgave 4.24}
Als $s^{[-1]}(L) := \{x : s(x) \cap L \neq \emptyset\}$ en $s$ verbind 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.

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. Er zal de 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}
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 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'.

\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
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}


\begin{thebibliography}{1}
\bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
languages and automata theory }, \emph{Cambridge University Press}, 2009.
\end{thebibliography}
\newpage
\end{document}