source: liacs/TPFL2010/assignment1/report.tex@ 225

Last change on this file since 225 was 225, checked in by Rick van der Zwet, 14 years ago

Opgave 3.20.

File size: 2.4 KB
Line 
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}
10\usepackage[pdftex]{graphicx}
11\usepackage{url}
12\usepackage{amssymb,amsmath}
13\usepackage{lipsum}
14\usepackage{float}
15
16\floatstyle{ruled}
17\newfloat{algoritm}{thp}{lop}
18\floatname{algoritm}{Algoritme}
19
20\title{Opdracht 1 \\
21\large{Topics on Parsing and Formal Languages - fall 2010}}
22\author{Rick van der Zwet\\
23 \texttt{<hvdzwet@liacs.nl>}}
24\date{\today}
25
26
27\begin{document}
28\newcommand{\DFA}{\emph{DFA}~}
29\newcommand{\qed}{\hfill \ensuremath{\Box}}
30\maketitle
31\begin{abstract}
32Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
33\cite{JS2009} gebruikt bij het college. In deze opdracht zullen zeven opgaven
34(3,20,22,47,54,68,69) van hoofdstuk 3 behandeld worden.
35\end{abstract}
36
37\section{Opgave 3.3}
38Als $L \subseteq \Sigma^*$ is regulier dan is de taal
39\begin{equation}
402L := {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
41\end{equation}
42regulier. Zie dat er een `verdubbeling' optreed van symbolen, dit gedrag is de
43modeleren in een \DFA. Omdat $L$ regulier is bestaat er een \DFA $M =
44(Q,\Sigma,\delta,q_0,F)$ die $L$ beschijft. Construreer nu een nieuwe \DFA $P$
45die de nieuwe taal $2L$ gaat beschrijven, neem hiervoor het alfabet ($\Sigma$),
46en de begintoestand $q_0$ over van $L$. De toestanden ($Q$) worden verdubbeled.
47$voor~alle~q \in Q:~voeg~q'~toe~aan~Q$. Neem ook de transities over van $M$,
48maar maak aanpassingen zodaning dat de nieuwe toestanden ook gelezen worden. Dus
49$\delta(q,x)$ wordt $\delta(q,q'),\delta(q',x)$. De acceptatie toestand $F$
50moet ook aangepast worden, door de oude acceptatie $q$ te vervangen door $q'$.
51
52De nieuwe \DFA $P$ beschijft $2L$ en dus is $2L$ regulier.
53\qed
54
55
56\section{Opgave 3.20}
57Laat $\Sigma = {0,1}$ zijn. Een voorbeeld van de taal $L \subseteq
58\Sigma^*$ voor welke geldt dat, de Myhill-Nerode\cite{JS2009}[pg. 77--81]
59gelijkheids relatie $R_L$ de eigenschap heeft dat elk woord in $\Sigma^*$ zijn
60eigen equivalentie klasse is, is de taal $L = {0,1}^+$.
61
62\section{Opgave 3.22}
63\section{Opgave 3.47}
64\section{Opgave 3.54}
65\section{Opgave 3.68}
66\section{Opgave 3.69}
67
68\begin{thebibliography}{1}
69\bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
70languages and automata theory }, \emph{Cambridge University Press}, 2009.
71\end{thebibliography}
72\newpage
73\end{document}
Note: See TracBrowser for help on using the repository browser.