[2] | 1 | %
|
---|
| 2 | % $Id: report.tex 571 2008-04-20 17:31:04Z rick $
|
---|
| 3 | %
|
---|
| 4 |
|
---|
| 5 | \documentclass[12pt,a4paper]{article}
|
---|
| 6 |
|
---|
| 7 | \frenchspacing
|
---|
| 8 | \usepackage[english,dutch]{babel}
|
---|
| 9 | \selectlanguage{dutch}
|
---|
[224] | 10 | \usepackage[pdftex]{graphicx}
|
---|
[2] | 11 | \usepackage{url}
|
---|
| 12 | \usepackage{amssymb,amsmath}
|
---|
[224] | 13 | \usepackage{float}
|
---|
[226] | 14 | \usepackage{tikz}
|
---|
[2] | 15 |
|
---|
[226] | 16 | \usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}
|
---|
| 17 |
|
---|
| 18 |
|
---|
| 19 |
|
---|
| 20 | \setlength\parindent{0pt}
|
---|
| 21 | \setlength\parskip{\baselineskip}
|
---|
[224] | 22 | \floatstyle{ruled}
|
---|
| 23 | \newfloat{algoritm}{thp}{lop}
|
---|
| 24 | \floatname{algoritm}{Algoritme}
|
---|
| 25 |
|
---|
| 26 | \title{Opdracht 1 \\
|
---|
| 27 | \large{Topics on Parsing and Formal Languages - fall 2010}}
|
---|
[2] | 28 | \author{Rick van der Zwet\\
|
---|
[224] | 29 | \texttt{<hvdzwet@liacs.nl>}}
|
---|
[2] | 30 | \date{\today}
|
---|
| 31 |
|
---|
[224] | 32 |
|
---|
[2] | 33 | \begin{document}
|
---|
[224] | 34 | \newcommand{\DFA}{\emph{DFA}~}
|
---|
| 35 | \newcommand{\qed}{\hfill \ensuremath{\Box}}
|
---|
[2] | 36 | \maketitle
|
---|
[224] | 37 | \begin{abstract}
|
---|
| 38 | Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
|
---|
| 39 | \cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
|
---|
| 40 | (3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden.
|
---|
| 41 | \end{abstract}
|
---|
[2] | 42 |
|
---|
[224] | 43 | \section{Opgave 3.3}
|
---|
| 44 | Als $L \subseteq \Sigma^*$ is regulier dan is de taal
|
---|
| 45 | \begin{equation}
|
---|
| 46 | 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
|
---|
| 47 | \end{equation}
|
---|
| 48 | regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
|
---|
| 49 | modeleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
|
---|
| 50 | (Q,\Sigma,\delta,q_0,F)$ die $L$ beschijft. Construreer nu een nieuwe \DFA $P$
|
---|
| 51 | die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
|
---|
| 52 | en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeled.
|
---|
| 53 | $voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
|
---|
| 54 | maar maak aanpassingen zodaning dat de nieuwe toestanden ook gelezen worden. Dus
|
---|
| 55 | $\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$
|
---|
| 56 | moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$.
|
---|
[226] | 57 | \\
|
---|
[224] | 58 | De nieuwe \DFA $P$ beschijft $2L$ en dus is $2L$ regulier.
|
---|
| 59 | \qed
|
---|
| 60 |
|
---|
| 61 |
|
---|
[225] | 62 | \section{Opgave 3.20}
|
---|
| 63 | Laat $\Sigma = {0,1}$ zijn. Een voorbeeld van de taal $L \subseteq
|
---|
| 64 | \Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
|
---|
| 65 | gelijkheids relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
|
---|
[226] | 66 | eigen equivalentie klasse is. Dit wilt zeggen dat voor alle $z \in \Sigma^*$,
|
---|
| 67 | is er een $xz \in L$ dan en slechts als $yz \in L$. Omdat hier gezocht wordt
|
---|
| 68 | naar een taal waarbij de woorden allemaal equivalentie klassen opzich zijn, zal
|
---|
| 69 | alle elementen met elkaar vergeleken kunnen worden dmv $R_L$ en hier mogen geen
|
---|
| 70 | positieve 'gevallen' uitkomen.
|
---|
[224] | 71 |
|
---|
[226] | 72 | Een mooi voorbeeld is de taal van \emph{PRIMES2}\cite{JS2009}[pg. 2], waarbij
|
---|
| 73 | de priemgetallen in een binair stelsel worden vertegenwoordigd. Door op unieke
|
---|
| 74 | 'start' van de woorden zullen deze nooit in elkaar vervallen en zal dus elk
|
---|
| 75 | woord zijn eigen klasse zijn.
|
---|
| 76 |
|
---|
| 77 |
|
---|
[224] | 78 | \section{Opgave 3.22}
|
---|
[226] | 79 | Om aan te tonen dat een \emph{2DFA} exponentioneel meer expressief is dan een
|
---|
| 80 | \DFA voor bepaalde talen kijken we naar de volgende taal; Laat $n$ een integer
|
---|
| 81 | $\ge1$ en $F_n \subseteq \{0,1,2,3,4\}^*$ als volgende gedefineerd:
|
---|
| 82 | \begin{equation}
|
---|
| 83 | 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\}
|
---|
| 84 | \end{equation}
|
---|
| 85 |
|
---|
| 86 | Als eerste kan de $F_n$ door een \emph{2DFA} van $O(n)$ toestanden geaccepteerd
|
---|
| 87 | worden, welke aan te tonen is door eerst te kijken naar de eigenschappen van
|
---|
| 88 | $F_n$ hierbij is de zien dat de $0$-reeks van de lengte $i^k$ zowel voor als na
|
---|
| 89 | de $2^k$ moet voorkomen. Waarbij $2^k$ aangeeft, waar deze $0$-reeks gevonden
|
---|
| 90 | kan worden e.g. bij welke $i_x$. De \emph{2DFA} moet dus twee dingen doen. Het
|
---|
| 91 | aantal keer nul op twee plekken vergelijken. Waarbij 1 plek vast staat en de
|
---|
| 92 | tweede plek variable wordt gedefineerd. Dit lijkt mij controleren op twee los
|
---|
| 93 | staande feiten. Hiervoor heb ik \underline{geen} antwoord gevonden. Ik kan
|
---|
| 94 | enkel wat voor $O(n^2)$ bedenken, welke een idee is in Figuur~\ref{fig:idee}
|
---|
| 95 | uitgewerkt is.
|
---|
| 96 |
|
---|
| 97 |
|
---|
| 98 | \begin{figure}
|
---|
| 99 | \label{fig:idee}
|
---|
| 100 | \center
|
---|
| 101 | \begin{tikzpicture}
|
---|
| 102 | \node[place,pin={[pin edge={style=<-,blue,thick,decorate,decoration={snake, pre length=4pt}}]left:}] (q0) {};
|
---|
| 103 | \node[place] (q1) [below=of q0] {};
|
---|
| 104 | \node[place] (q2) [below=of q1] {};
|
---|
| 105 | \node[place,pin={[pin edge={style=-<,thick,decorate,decoration={snake, pre length=4pt}}]below:}] (q3) [below=of q2] {};
|
---|
| 106 | \node[place] (q01) [right=3cm of q1] {};
|
---|
| 107 | \node[place] (q02) [right=3cm of q2] {};
|
---|
| 108 | \path[->]
|
---|
| 109 | (q0) edge [decorate,decoration={snake}] node[left] {goto-2} (q1)
|
---|
| 110 | (q1) edge node[left] {2} (q2)
|
---|
| 111 | (q2) edge node[left] {2} (q3)
|
---|
| 112 | (q1) edge [decorate,decoration={snake}] node[above] {0-length-check} (q01)
|
---|
| 113 | (q2) edge [decorate,decoration={snake}] node[above] {0-length-check} (q02)
|
---|
| 114 | ;
|
---|
| 115 | \end{tikzpicture}
|
---|
| 116 | \caption{Idee voor Opdracht 2.22a}
|
---|
| 117 | \end{figure}
|
---|
| 118 |
|
---|
| 119 | Om te laten zien dat een \DFA minstens $n^n$ toestanden nodig heeft moet je
|
---|
| 120 | gebruik maken van het feit dan een \DFA niet terug kan lopen. Het zal dus een
|
---|
| 121 | `geheugen' moeten maken om het maximale $0$ woord voor de `splitsing' ($2^k$)
|
---|
| 122 | te kunnen onthouden om zo te kijken of het overeen komt het $0$ woord na de
|
---|
| 123 | `splitsing'. Omdat je voor elke $F_i$ waarbij $1 \ge i \ge n$ minimaal $n$
|
---|
| 124 | toestanden nodig hebt om te kunnen tellen en hiervan weer $n$ unieke sets
|
---|
| 125 | bestaan, heb je dus minimaal $n^n$ toestanden nodig.
|
---|
| 126 |
|
---|
| 127 |
|
---|
| 128 |
|
---|
| 129 |
|
---|
[224] | 130 | \section{Opgave 3.47}
|
---|
| 131 | \section{Opgave 3.54}
|
---|
| 132 | \section{Opgave 3.68}
|
---|
| 133 | \section{Opgave 3.69}
|
---|
| 134 |
|
---|
| 135 | \begin{thebibliography}{1}
|
---|
| 136 | \bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
|
---|
| 137 | languages and automata theory }, \emph{Cambridge University Press}, 2009.
|
---|
[2] | 138 | \end{thebibliography}
|
---|
| 139 | \newpage
|
---|
| 140 | \end{document}
|
---|