Ignore:
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:
3 copied

Legend:

Unmodified
Added
Removed

  • liacs/TPFL2010/assignment2/report.tex

    r232 r238  
    2525\floatname{algoritm}{Algoritme}
    2626
    27 \title{Opdracht 1 \\
     27\title{Opdracht 2 \\
    2828\large{Topics on Parsing and Formal Languages - fall 2010}}
    2929\author{Rick van der Zwet\\
    … …  
    3535\newcommand{\DFA}{\emph{DFA}~}
    3636\newcommand{\qed}{\hfill \ensuremath{\Box}}
     37\newcommand{\all}{\Sigma^*}
    3738\maketitle
    3839\begin{abstract}
    3940Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
    4041\cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
    41 (3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden. De opgaven zijn
    42 willekeurig gekozen met behulp van een kans generator, het kans dus zijn dat
    43 niet alle onderwerpen van hoofdstuk 3 behandeld worden.
     42(9, 18, 24, 26, 32, 35, 41) van hoofdstuk 4 behandeld worden. De opgaven zijn
     43willekeurig gekozen met behulp van een kans generator, het kan dus zijn dat
     44niet alle onderwerpen van hoofdstuk 4 behandeld worden.
    4445\end{abstract}
    4546
    46 \section{Opgave 3.3}
    47 Als $L \subseteq \Sigma^*$ is regulier dan is de taal
    48 \begin{equation}
    49 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
    50 \end{equation}
    51 regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
    52 modelleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
    53 (Q,\Sigma,\delta,q_0,F)$ die $L$ beschrijft.  Construeer nu een nieuwe \DFA $P$
    54 die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
    55 en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeld.
    56 $voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
    57 maar maak aanpassingen zodanig dat de nieuwe toestanden ook gelezen worden. Dus
    58 $\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$
    59 moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$.
    60 \\
    61 De nieuwe \DFA $P$ beschrijft $2L$ en dus is $2L$ regulier.
    62 \qed
     47\section{Opgave 4.9}
     48Laat $L \subseteq \all$ de taal zijn en defineer $\sigma(L) = \{x \in \all : xy
     49\in voor~alle~y \in \all\}$. Als $L$ context-vrij is $\sigma(L)$ ook
     50context-vrij. Omdat $y = \all$ is dit een reguliere taal. $xy$ zal dan een
     51context-vrije taal zijn (gesloten onder concatenatie). $xy \in L$ is vereniging
     52van $xy$ met $L$, welke onder context-vrije talen gesloten is. Hierdoor zal
     53$\sigma(L)$ (een subset) ook weer context-vrij zijn.
    6354
    6455
    65 \section{Opgave 3.20}
    66 Laat $\Sigma = {0,1}$ zijn. Een voorbeeld van de taal $L \subseteq
    67 \Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
    68 gelijkheid relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
    69 eigen equivalentie klasse is. Dit wilt zeggen dat voor alle $z \in \Sigma^*$,
    70 is er een $xz \in L$ dan en slechts als $yz \in L$. Omdat hier gezocht wordt
    71 naar een taal waarbij de woorden allemaal equivalentie klassen op-zich zijn, zal
    72 alle elementen met elkaar vergeleken kunnen worden door middel van $R_L$ en hier mogen geen
    73 positieve 'gevallen' uitkomen.
     56\section{Opgave 4.18}
     57Als $L$ een context-vrije taal is en $R$ een reguliere taal dan de rechter
     58quotient $L/R = \{x \in \all: \exists y \in R~zodat~xy \in L \}$ is ook een
     59context-vrije taal. $xy$ zijn de woorden in $L$ waarbij geldt dat de suffix
     60$y$ regulier is. Stel dat $x$ geen context-vrije taal was. Dan zou $xy$ ook
     61geen context-vrije taal zijn. Wat niet kan welke $L$ context-vrij is en in die
     62hoedanigheid ook de subsets van $L$.
    7463
    75 Een mooi voorbeeld is de taal van \emph{PRIMES2}\cite{JS2009}[pg. 2], waarbij
    76 de priemgetallen in een binair stelsel worden vertegenwoordigd. Door op unieke
    77 'start' van de woorden zullen deze nooit in elkaar vervallen en zal dus elk
    78 woord zijn eigen klasse zijn.
     64\section{Opgave 4.24}
     65Als $s^{[-1]}(L) := \{x : s(x) \cap L \neq \emptyset\}$ en $s$ verbind letters
     66met reguliere talen en $L$ is context-vrij. Dan is $s^{[-1]}(L)$ niet altijd
     67CFL, L een een verzameling kan zijn van alle talen van de letters waarbij geldt
     68dat de lengte van de letters even moet zijn, welke geen context-vrije
     69verzameling is.
     70
     71Hetzelfde probleem doet voor als $s$ letters aan context-vrije talen verbindt.
     72
     73\section{Opgave 4.26}
     74Gegeven een PDA $M$ kan je altijd een $M^{'}$ maken welke de eigenschap heeft dat
     75geen enkele stap het huidige symbool op de stapel vervangt (geen transities van
     76de vorm $(p,\gamma Y) \in \delta(q,a,X)~waarbij~X \neq Y$). Dus dat alle
     77stappen, of een symbool van de stapel afhalen, of een string van symbolen op
     78de stapel zetten. Dit is te doen door de hudige 'subsitutie' transities te
     79vervangen door een tweetal (gekoppelde) transities. Waarbij de eerste het
     80symbool eraf haalt en de tweede de gewenste symbolen er weer op zet.
     81
     82De bovengenoemde methode zorgt voor maar \'e\'en mogelijk pad. Er zal de de
     83DPDA structuur (indien present) dus niet aantasten.
    7984
    8085
    81 \section{Opgave 3.22}
    82 Om aan te tonen dat een \emph{2DFA} exponentieel meer expressief is dan een
    83 \DFA voor bepaalde talen kijken we naar de volgende taal; Laat $n$ een integer
    84 $\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefinieerd:
    85 \begin{equation}
    86   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\}
    87 \end{equation}
     86\section{Opgave 4.32}
     87Als $\psi$ een Parikh map is, dan zijn er lange Engelse woorden over een bepaald
     88alfabet voor specifieke eigenschappen. Voorbeelden zijn te vinden in de onderstaande tabel.
    8889
    89 Als eerste kan de $F_n$ door een \emph{2DFA} van $O(n)$ toestanden geaccepteerd
    90 worden, welke aan te tonen is door eerst te kijken naar de eigenschappen van
    91 $F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i^k$ zowel voor als na
    92 de $2^k$ moet voorkomen. Waarbij $2^k$ aangeeft, waar deze $0$-reeks gevonden
    93 kan worden e.g. bij welke $i_x$. De \emph{2DFA} moet dus twee dingen doen. Het
    94 aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de
    95 tweede plek variabele wordt gedefinieerd. Dit lijkt mij controleren op twee los
    96 staande feiten. Hiervoor heb ik \underline{geen} antwoord gevonden. Ik kan
    97 enkel wat voor $O(n^2)$ bedenken, welke een idee is in Figuur~\ref{fig:idee}
    98 uitgewerkt is.
     90\begin{tabular}{l | l | l }
     91eigenschap & woorden & alfabet \\
     92\hline \hline
     93$\psi(w)$ alle items gelijk aan 1 & dutchwomen & $\{d,u,t,c,h,w,o,m,e,n\}$\\
     94$\psi(w)$ alle items gelijk aan 2 & tomtom & $\{t,o,m\}$\\
     95$\psi(w)$ alle items gelijk aan 3 & sestettes & $\{s,e,t\}$\\
     96$\psi(w)$ alle items $\ge$ 2 & unprosperousness & $\{e,n,o,p,r,s,u\}$\\
     97$\psi(w)$ $(1,2,2,3,3,3)$ & chincherinchee & $\{r,i,n,c,h,e\}$\\
     98\end{tabular}
    9999
    100100
    101 \begin{figure}
    102 \center
    103 \begin{tikzpicture}
    104 \node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q0) {};
    105 \node[place] (q1) [below=of q0] {};
    106 \node[place] (q2) [below=of q1] {};
    107 \node[place,pin={[pin edge={style=-<,thick,decorate,decoration={snake, pre length=4pt}}]below:}] (q3) [below=of q2] {};
    108 \node[place] (q01) [right=3cm of q1] {};
    109 \node[place] (q02) [right=3cm of q2] {};
    110 \path[->]
    111           (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q1)
    112           (q1) edge              node[left] {2} (q2)
    113           (q2) edge              node[left] {2} (q3)
    114           (q1) edge [decorate,decoration={snake}] node[above] {0-length-check} (q01)
    115           (q2) edge [decorate,decoration={snake}] node[above] {0-length-check} (q02)
    116         ;
    117 \end{tikzpicture}
    118 \caption{Idee voor Opdracht 2.22a}
    119 \label{fig:idee}
    120 \end{figure}
    121 
    122 Om te laten zien dat een \DFA minstens $n^n$ toestanden nodig heeft moet je
    123 gebruik maken van het feit dan een \DFA niet terug kan lopen. Het zal dus een
    124 `geheugen' moeten maken om het maximale $0$ woord voor de `splitsing' ($2^k$)
    125 te kunnen onthouden om zo te kijken of het overeen komt het $0$ woord na de
    126 `splitsing'. Omdat je voor elke $F_i$ waarbij $1 \ge i \ge n$ minimaal $n$
    127 toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
    128 bestaan, heb je dus minimaal $n^n$ toestanden nodig.
    129 
    130 \section{Opgave 3.47}
    131 
    132 Om te bewijzen dat `de klasse van talen geaccepteerd door \DFA' => `de klasse van
    133 talen gespecificeerd door de reguliere expressies'\cite{JS2009}[Theorem 1.4.2, (b) => (a)]
    134 aan de hand van het volgende voorbeeld:
    135 Laat $M = (Q,\Sigma, \delta, q_1,F)$ een \DFA zijn, waarbij $Q =
    136 \{q_1,q_2,\ldots,q_n\}$. Definieer nu $R_{i,j,k}$ als de taal van alle woorden
    137 die van toestand $i$ naar toestand $j$ gaan zonder door toestanden te gaan die
    138 hoger als $k$ genummerd zijn.
    139 
    140 Om dit te doen is een recursieve formule nodig, welke $R_{i,j,k}$ als invoer
    141 heeft. a) Kijk welke transities er mogelijk zijn in $\delta$ met toestand $i$ als
    142 begin positie. Plaats deze op de `stapel'. b) Werk de elementen op de stapel
    143 stuk voor stuk af volgens dezelfde methodiek. Stop pas als de $\delta$
    144 resultaat $j$ bevat. Let erop dat oneindige herhalingen gedetecteerd moeten
    145 worden om het algoritme te laten termineren. Je kan het zien als het volledig
    146 doorzoeken van een boom met in de wortel de knoop $i$.
    147 
    148 \section{Opgave 3.54}
    149 
    150 Laat $\Sigma = \{1,2,3,\ldots,n\}$ zijn en definieer:
    151 \begin{equation}
    152 L_n = \{w \in \Sigma^* : |w|_i = 1~voor~alle~i\}
    153 \end{equation}
    154 Dit zijn dus de woorden waarbij alle elementen precies \'{e}\'{e}n keer in voor
    155 komen. Bijvoorbeeld $L_3 = \{123,132,213,231,312,321\}$.
    156 
    157 Om te laten zijn dat er minimal een reguliere expressie van lengte $2^{n-1}$
    158 nodig is om $L_n$ te specificeren, moet de \emph{Myhill-Nerode} stelling
    159 toegepast worden. Vanwege de eigenschap dat prefix uniek is, zat het nooit
    160 mogelijk worden om aan beiden woorden hetzelfde toe te voegen zodanig dat ze in
    161 elkaars klasse terecht komen. (elk `bit' informatie is relevant). Voor alle
    162 klasse zal dus apart gekeken worden of aan de eisen voldaan wordt. Om dus alle
    163 getallen $n$ van de string te controleren of zij uniek is zijn minimaal
    164 $2^{n-1}$ toestanden nodig.
    165 
    166 Echter voor $\overline{L_n}$  is wel een reguliere expressie te vinden en wel
    167 in de grootte $O(n^2)$. Door simpelweg voor elke $i \in \Sigma^*$ een reguliere
    168 expressie te maken van de vorm $x^*~i~x^*~i~x^*$ waarbij $x = Sigma^* - i$.
    169 
    170 \section{Opgave 3.68}
    171 
    172 Voor een woord $w \in \Sigma^*$, is een palc($w$) de korte palindroom $x$
    173 zodanig dat $w$ een prefix is van $x$. en palc($L$) = $\bigcup_{w \in L}\{palc(w)\}$.
    174 
    175 Om te laten zien dat palc($w$) = $wt^{-1}w^R$, waarbij $wt^{-1}$ het woord is $w$
    176 waar het suffix $t$ eraf gehaald is en $t$ de langste palindroom suffix van $w$
    177 is, moet er gebruik gemaakt worden van een tegenstelling. Als $w$ nog een
    178 palindroom aan het einde zal bevatten $uu$, dan ziet $x$ er als volgt uit
    179 $wuuuuw$, dit is niet de korte palindroom ($ww$), welke $uuuu$ er nog makkelijk
    180 uit weggehaald had kunnen worden. Een willekeurige suffix van $w$ kan ook geen
    181 palindroom vormen die nog `weggesneden' kan worden, omdat hij anders al in den
    182 beginne een palindroom had moeten zijn.
    183 
    184 Als $L$ is regulier, dan is palc($L$) ook regulier, welke er een unieke
    185 `vertaling' van een woord $w$ naar zijn palc($w$). De nieuwe woorden zullen in
    186 het slechtste geval evenveel blijven, maar de taal kan ook kleiner worden.
    187 
    188 De andere kant op geldt dit \underline{niet}, als $L$ regulier is, dan is het
    189 onbeslist of palc\textsuperscript{-1}($L$) ook regulier is. Het kan namelijk
    190 zeer goed dat een (ingewikkelde) functie die woorden genereerde welke een
    191 palindroom zijn en die aan een vast prefix ($p$) toegevoegd. De \emph{palc}
    192 functie zal deze allen naar \'{e}\'{e}n woord omzetten, welke dan regulier is.
     101\section{Opgave 4.35}
    193102
    194103
    195 \section{Opgave 3.69}
     104\section{Opgave 4.41}
    196105
    197 Laat $x_1,x_2,\ldots,x_k \in \Sigma^*$. Om te laten zien dat $\Sigma^* -
    198 x_{1}^{*}x_{2}^{*} \cdots x_{k}^*$ eindig is dan en slechts als $|\Sigma| = 1$
    199 en gcd($|x_1|,|x_2|,\ldots,|x_k|$) = 1 moet er een paar dingen bewezen worden
    200 a) aantonen dat het \underline{niet} geldt voor de tegenvoorbeelden a) $gcd
    201 > 1$ b) $|\Sigma| > 1$ en tevens moet aangetoond worden waarom de eindigheid
    202  voor dit specifieke geval geldt.
    203106
    204 Merk op dat met een gcd van 1 alle getallen in de verzameling \{1,
    205 priemgetallen\} zitten. Bij een alfabet van 1 letter hoeft er enkel maar
    206 gesproken worden over lengtes. Standaard zitten alle lengtes in de taal.
    207 Aangezien de `deel-lengtes' ($x_1,x_2,\ldots,x_k$) nul of meer keer in de
    208 verzameling in de verzameling mogen zitten. Zal je uiteindelijk overblijven met
    209 een eindige set lengtes. In het geval dat er lengte 1 gevonden wordt, zal zelfs
    210 de lege set het antwoord zijn.
    211 
    212 a) Als $|\Sigma| > 1$, bijvoorbeeld $\{1,2\}$ dan kan er een oneindige
    213 verzameling gemaakt worden, door $x_1,x_2,\ldots,x_k \in 1^*$. De $2*$ zal dan een
    214 oneindige verzameling vormen.
    215 
    216 b) $gcd > 1$, bijvoorbeeld $2$ dan kan er een oneindige verzameling gemaakt
    217 worden, doordat niet alle woorden gemaakt kunnen worden. Enkel worden van
    218 `even' lengte in dit geval. Waardoor de `oneven' woorden een eindige string
    219 gaan vormen. Bij grotere waardes ($r$) kunnen ook 'groepen' (de $|r|* - 1$)
    220 bijvoorbeeld niet meer bereikt worden, welke dan tot een oneindige verzameling
    221 kunnen groeien.
    222107
    223108\begin{thebibliography}{1}
Note: See TracChangeset for help on using the changeset viewer.