Index: /liacs/TPFL2010/assignment2/latex.mk
===================================================================
--- /liacs/TPFL2010/assignment2/latex.mk	(revision 238)
+++ /liacs/TPFL2010/assignment2/latex.mk	(revision 238)
@@ -0,0 +1,74 @@
+# Rick van der Zwet <rick@wzoeterwoude.net>
+# Licence: BSD
+# Descrip: LaTex file parser
+# $Id: latex.mk 571 2008-04-20 17:31:04Z rick $
+
+TARGET = report
+LATEX = latex
+XDVI = xdvi -geometry +700+0
+TEX = latex -halt-on-error
+DVIPDF = dvipdf
+ASPELL = aspell
+ASPELL_ARGS = -c --mode=tex -x
+
+#XXX: Make me dynamic
+VIEWPDF = evince
+VIEWPS = gv -geometry +700+0
+.SUFFIXES: .pdf .ps
+
+PAGE ?= 1
+
+help:
+	@echo "Usage Makefile <option>"
+
+doc-all: doc-distclean buildpdf
+
+view: viewpdf
+
+viewps: buildps
+	$(VIEWPS) -page=$(PAGE) $(TARGET).ps
+
+buildps: $(SOURCE) $(TARGET).dvi
+	dvips $(TARGET).dvi
+
+viewdvi: builddvi
+	$(XDVI) $(TARGET) +$(PAGE)
+
+builddvi: $(SOURCE) $(TARGET).dvi
+
+doc-clean:
+	rm -vf *.aux *.log *toc *.out *.bak *.m.tex
+
+doc-distclean: doc-clean
+	rm -vf $(TARGET).dvi $(TARGET).pdf $(PROGRAM)
+
+buildpdf: $(SOURCE) $(TARGET).pdf
+
+viewpdf: buildpdf
+	$(VIEWPDF) -p $(PAGE) $(TARGET).pdf
+
+spell: spell-en
+
+spell-nl: $(TARGET).tex
+	$(ASPELL) -l nl -p ~/aspell-n.dic $(ASPELL_ARGS) $<
+
+spell-en: $(TARGET).tex
+	$(ASPELL) -l en -p ~/aspell-en.dic $(ASPELL_ARGS) $<
+
+#.dvi.pdf:
+#	$(DVIPDF) $? $@
+
+.tex.pdf:
+	pdflatex -halt-on-error $?
+	pdflatex -halt-on-error $?
+
+.tex.dvi:
+	$(TEX) $? $@
+	$(TEX) $? $@
+
+.gs.png:
+	$(GNUPLOT) $?
+
+%.m.tex: %.m
+	highlight --include-style --linenumbers --no-doc \
+	  --latex --input $< --output $@
Index: /liacs/TPFL2010/assignment2/report.tex
===================================================================
--- /liacs/TPFL2010/assignment2/report.tex	(revision 238)
+++ /liacs/TPFL2010/assignment2/report.tex	(revision 238)
@@ -0,0 +1,113 @@
+%
+% $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, 35, 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
+quotient $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 hudige 'subsitutie' 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.35}
+
+
+\section{Opgave 4.41}
+
+
+
+\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}
