Changeset 238 for liacs/TPFL2010

Timestamp:

Nov 26, 2010, 8:46:24 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Laten we een deel van het werk alvast maar even opslaan.

Location:

liacs/TPFL2010/assignment2

Files:

• latex.mk (copied) (copied from liacs/TPFL2010/assignment1/latex.mk )
• report.pdf (copied) (copied from liacs/TPFL2010/assignment1/report.pdf )
• report.tex (copied) (copied from liacs/TPFL2010/assignment1/report.tex ) (2 diffs)

liacs/TPFL2010/assignment2/report.tex

@@ -25 +25 @@
 \floatname{algoritm}{Algoritme}
 
-\title{Opdracht 1 \\
+\title{Opdracht 2 \\
 \large{Topics on Parsing and Formal Languages - fall 2010}}
 \author{Rick van der Zwet\\
@@ -35 +35 @@
 \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
-(3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden. De opgaven zijn
-willekeurig gekozen met behulp van een kans generator, het kans dus zijn dat
-niet alle onderwerpen van hoofdstuk 3 behandeld worden.
+(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 3.3}
-Als $L \subseteq \Sigma^*$ is regulier dan is de taal
-\begin{equation}
-2L := {a_1,a_1,a_2,a_2,\ldots,a_k,a_k}~:~elke~a_i \in \Sigma~en~a_1a_2{\cdots}a_k \in L
-\end{equation}
-regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
-modelleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
-(Q,\Sigma,\delta,q_0,F)$ die $L$ beschrijft.  Construeer nu een nieuwe \DFA $P$
-die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
-en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeld.
-$voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
-maar maak aanpassingen zodanig dat de nieuwe toestanden ook gelezen worden. Dus
-$\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$
-moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$.
-\\
-De nieuwe \DFA $P$ beschrijft $2L$ en dus is $2L$ regulier.
-\qed
+\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 3.20}
-Laat $\Sigma = {0,1}$ zijn. Een voorbeeld van de taal $L \subseteq
-\Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
-gelijkheid relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
-eigen equivalentie klasse is. Dit wilt zeggen dat voor alle $z \in \Sigma^*$,
-is er een $xz \in L$ dan en slechts als $yz \in L$. Omdat hier gezocht wordt
-naar een taal waarbij de woorden allemaal equivalentie klassen op-zich zijn, zal
-alle elementen met elkaar vergeleken kunnen worden door middel van $R_L$ en hier mogen geen
-positieve 'gevallen' uitkomen. 
+\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$.
 
-Een mooi voorbeeld is de taal van \emph{PRIMES2}\cite{JS2009}[pg. 2], waarbij
-de priemgetallen in een binair stelsel worden vertegenwoordigd. Door op unieke
-'start' van de woorden zullen deze nooit in elkaar vervallen en zal dus elk
-woord zijn eigen klasse zijn.
+\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 3.22}
-Om aan te tonen dat een \emph{2DFA} exponentieel meer expressief is dan een
-\DFA voor bepaalde talen kijken we naar de volgende taal; Laat $n$ een integer
-$\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefinieerd:
-\begin{equation}
-  F_n = \{3~0^{i_1}~1~0^{i_2} \cdots 1~0^{i_n}~2^k~0^{i_k}~4 : 1 \ge k,j,i_j \ge n\}
-\end{equation}
+\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.
 
-Als eerste kan de $F_n$ door een \emph{2DFA} van $O(n)$ toestanden geaccepteerd
-worden, welke aan te tonen is door eerst te kijken naar de eigenschappen van
-$F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i^k$ zowel voor als na
-de $2^k$ moet voorkomen. Waarbij $2^k$ aangeeft, waar deze $0$-reeks gevonden
-kan worden e.g. bij welke $i_x$. De \emph{2DFA} moet dus twee dingen doen. Het
-aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de
-tweede plek variabele wordt gedefinieerd. Dit lijkt mij controleren op twee los
-staande feiten. Hiervoor heb ik \underline{geen} antwoord gevonden. Ik kan
-enkel wat voor $O(n^2)$ bedenken, welke een idee is in Figuur~\ref{fig:idee}
-uitgewerkt is.
+\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}
 
 
-\begin{figure}
-\center
-\begin{tikzpicture}
-\node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q0) {};
-\node[place] (q1) [below=of q0] {};
-\node[place] (q2) [below=of q1] {};
-\node[place,pin={[pin edge={style=-<,thick,decorate,decoration={snake, pre length=4pt}}]below:}] (q3) [below=of q2] {};
-\node[place] (q01) [right=3cm of q1] {};
-\node[place] (q02) [right=3cm of q2] {};
-\path[->] 
-          (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q1)
-          (q1) edge              node[left] {2} (q2)
-          (q2) edge              node[left] {2} (q3)
-          (q1) edge [decorate,decoration={snake}] node[above] {0-length-check} (q01)
-          (q2) edge [decorate,decoration={snake}] node[above] {0-length-check} (q02)
-        ;
-\end{tikzpicture}
-\caption{Idee voor Opdracht 2.22a}
-\label{fig:idee}
-\end{figure}
-
-Om te laten zien dat een \DFA minstens $n^n$ toestanden nodig heeft moet je
-gebruik maken van het feit dan een \DFA niet terug kan lopen. Het zal dus een
-`geheugen' moeten maken om het maximale $0$ woord voor de `splitsing' ($2^k$)
-te kunnen onthouden om zo te kijken of het overeen komt het $0$ woord na de
-`splitsing'. Omdat je voor elke $F_i$ waarbij $1 \ge i \ge n$ minimaal $n$
-toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
-bestaan, heb je dus minimaal $n^n$ toestanden nodig.
-
-\section{Opgave 3.47}
-
-Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' => `de klasse van
-talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) => (a)]
-aan de hand van het volgende voorbeeld:
-Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q =
-\{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden
-die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die
-hoger als $k$ genummerd zijn.
-
-Om dit te doen is een recursieve formule nodig, welke $R_{i,j,k}$ als invoer
-heeft. a) Kijk welke transities er mogelijk zijn in $\delta$ met toestand $i$ als
-begin positie. Plaats deze op de `stapel'. b) Werk de elementen op de stapel
-stuk voor stuk af volgens dezelfde methodiek. Stop pas als de $\delta$
-resultaat $j$ bevat. Let erop dat oneindige herhalingen gedetecteerd moeten
-worden om het algoritme te laten termineren. Je kan het zien als het volledig
-doorzoeken van een boom met in de wortel de knoop $i$.
-
-\section{Opgave 3.54}
-
-Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en definieer:
-\begin{equation}
-L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\}
-\end{equation}
-Dit zijn dus de woorden waarbij alle elementen precies \'{e}\'{e}n keer in voor
-komen. Bijvoorbeeld $L_3 = \{123,132,213,231,312,321\}$.
-
-Om te laten zijn dat er minimal een reguliere expressie van lengte $2^{n-1}$
-nodig is om $L_n$ te specificeren, moet de \emph{Myhill-Nerode} stelling
-toegepast worden. Vanwege de eigenschap dat prefix uniek is, zat het nooit
-mogelijk worden om aan beiden woorden hetzelfde toe te voegen zodanig dat ze in
-elkaars klasse terecht komen. (elk `bit' informatie is relevant). Voor alle
-klasse zal dus apart gekeken worden of aan de eisen voldaan wordt. Om dus alle
-getallen $n$ van de string te controleren of zij uniek is zijn minimaal
-$2^{n-1}$ toestanden nodig.
-
-Echter voor $\overline{L_n}$  is wel een reguliere expressie te vinden en wel
-in de grootte $O(n^2)$. Door simpelweg voor elke $i \in \Sigma^*$ een reguliere
-expressie te maken van de vorm $x^*~i~x^*~i~x^*$ waarbij $x = Sigma^* - i$. 
-
-\section{Opgave 3.68}
-
-Voor een woord $w \in \Sigma^*$, is een palc($w$) de korte palindroom $x$
-zodanig dat $w$ een prefix is van $x$. en palc($L$) = $\bigcup_{w \in L}\{palc(w)\}$.
-
-Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$
-waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$
-is, moet er gebruik gemaakt worden van een tegenstelling. Als $w$ nog een
-palindroom aan het einde zal bevatten $uu$, dan ziet $x$ er als volgt uit
-$wuuuuw$, dit is niet de korte palindroom ($ww$), welke $uuuu$ er nog makkelijk
-uit weggehaald had kunnen worden. Een willekeurige suffix van $w$ kan ook geen
-palindroom vormen die nog `weggesneden' kan worden, omdat hij anders al in den
-beginne een palindroom had moeten zijn.
-
-Als $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke
-`vertaling' van een woord $w$ naar zijn palc($w$). De nieuwe woorden zullen in
-het slechtste geval evenveel blijven, maar de taal kan ook kleiner worden.
-
-De andere kant op geldt dit \underline{niet}, als $L$ regulier is, dan is het
-onbeslist of palc\textsuperscript{-1}($L$) ook regulier is. Het kan namelijk
-zeer goed dat een (ingewikkelde) functie die woorden genereerde welke een
-palindroom zijn en die aan een vast prefix ($p$) toegevoegd. De \emph{palc}
-functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is.
+\section{Opgave 4.35}
 
 
-\section{Opgave 3.69}
+\section{Opgave 4.41}
 
-Laat $x_1,x_2,\ldots,x_k \in \Sigma^*$. Om te laten zien dat $\Sigma^* -
-x_{1}^{*}x_{2}^{*} \cdots x_{k}^*$ eindig is dan en slechts als $|\Sigma| = 1$
-en gcd($|x_1|,|x_2|,\ldots,|x_k|$) = 1 moet er een paar dingen bewezen worden
-a) aantonen dat het \underline{niet} geldt voor de tegenvoorbeelden a) $gcd
-> 1$ b) $|\Sigma| > 1$ en tevens moet aangetoond worden waarom de eindigheid
- voor dit specifieke geval geldt.
 
-Merk op dat met een gcd van 1 alle getallen in de verzameling \{1,
-priemgetallen\} zitten. Bij een alfabet van 1 letter hoeft er enkel maar
-gesproken worden over lengtes. Standaard zitten alle lengtes in de taal.
-Aangezien de `deel-lengtes' ($x_1,x_2,\ldots,x_k$) nul of meer keer in de
-verzameling in de verzameling mogen zitten. Zal je uiteindelijk overblijven met
-een eindige set lengtes. In het geval dat er lengte 1 gevonden wordt, zal zelfs
-de lege set het antwoord zijn.
-
-a) Als $|\Sigma| > 1$, bijvoorbeeld $\{1,2\}$ dan kan er een oneindige
-verzameling gemaakt worden, door $x_1,x_2,\ldots,x_k \in 1^*$. De $2*$ zal dan een
-oneindige verzameling vormen.
-
-b) $gcd > 1$, bijvoorbeeld $2$ dan kan er een oneindige verzameling gemaakt
-worden, doordat niet alle woorden gemaakt kunnen worden. Enkel worden van
-`even' lengte in dit geval. Waardoor de `oneven' woorden een eindige string
-gaan vormen. Bij grotere waardes ($r$) kunnen ook 'groepen' (de $|r|* - 1$)
-bijvoorbeeld niet meer bereikt worden, welke dan tot een oneindige verzameling
-kunnen groeien. 
 
 \begin{thebibliography}{1}