Changeset 242 for liacs/TPFL2010/assignment3/report.tex
- Timestamp:
- Dec 1, 2010, 12:11:27 PM (14 years ago)
- File:
-
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
liacs/TPFL2010/assignment3/report.tex
r240 r242 25 25 \floatname{algoritm}{Algoritme} 26 26 27 \title{Opdracht 2\\27 \title{Opdracht 3 \\ 28 28 \large{Topics on Parsing and Formal Languages - fall 2010}} 29 29 \author{Rick van der Zwet\\ … … 39 39 \begin{abstract} 40 40 Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek 41 \cite{JS2009} gebruikt bij het college. In deze opdracht zullen zevenopgaven42 ( 9, 18, 24, 26, 32, 37, 41) van hoofdstuk 4behandeld worden. De opgaven zijn41 \cite{JS2009} gebruikt bij het college. In deze opdracht zullen vijf opgaven 42 (1, 5, 6, 8, 14) van hoofdstuk 5 behandeld worden. De opgaven zijn 43 43 willekeurig gekozen met behulp van een kans generator, het kan dus zijn dat 44 44 niet alle onderwerpen van hoofdstuk 4 behandeld worden. 45 45 \end{abstract} 46 46 47 \section{Opgave 4.9} 48 Laat $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 50 context-vrij. Omdat $y = \all$ is dit een reguliere taal. $xy$ zal dan een 51 context-vrije taal zijn (gesloten onder concatenatie). $xy \in L$ is vereniging 52 van $xy$ met $L$, welke onder context-vrije talen gesloten is. Hierdoor zal 53 $\sigma(L)$ (een subset) ook weer context-vrij zijn. 47 \section{Opgave 5.1} 54 48 55 49 56 \section{Opgave 4.18} 57 Als $L$ een context-vrije taal is en $R$ een reguliere taal dan de rechter 58 quotiënt $L/R = \{x \in \all: \exists y \in R~zodat~xy \in L \}$ is ook een 59 context-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 61 geen context-vrije taal zijn. Wat niet kan welke $L$ context-vrij is en in die 62 hoedanigheid ook de subsets van $L$. 63 64 \section{Opgave 4.24} 65 Als $s^{[-1]}(L) := \{x : s(x) \cap L \neq \emptyset\}$ en $s$ verbind letters 66 met reguliere talen en $L$ is context-vrij. Dan is $s^{[-1]}(L)$ niet altijd 67 CFL, L een een verzameling kan zijn van alle talen van de letters waarbij geldt 68 dat de lengte van de letters even moet zijn, welke geen context-vrije 69 verzameling is. 70 71 Hetzelfde probleem doet voor als $s$ letters aan context-vrije talen verbindt. 72 73 \section{Opgave 4.26} 74 Gegeven een PDA $M$ kan je altijd een $M^{'}$ maken welke de eigenschap heeft dat 75 geen enkele stap het huidige symbool op de stapel vervangt (geen transities van 76 de vorm $(p,\gamma Y) \in \delta(q,a,X)~waarbij~X \neq Y$). Dus dat alle 77 stappen, of een symbool van de stapel afhalen, of een string van symbolen op 78 de stapel zetten. Dit is te doen door de huidige substitutie' transities te 79 vervangen door een tweetal (gekoppelde) transities. Waarbij de eerste het 80 symbool eraf haalt en de tweede de gewenste symbolen er weer op zet. 81 82 De bovengenoemde methode zorgt voor maar \'e\'en mogelijk pad. Er zal de de 83 DPDA structuur (indien present) dus niet aantasten. 50 \section{Opgave 5.5} 84 51 85 52 86 \section{Opgave 4.32} 87 Als $\psi$ een Parikh map is, dan zijn er lange Engelse woorden over een bepaald 88 alfabet voor specifieke eigenschappen. Voorbeelden zijn te vinden in de onderstaande tabel. 89 90 \begin{tabular}{l | l | l } 91 eigenschap & 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} 53 \section{Opgave 5.6} 99 54 100 55 101 \section{Opgave 4.37} 102 perm($x$) is de set van alle permutaties van de letters van $x$. Voor talen is 103 perm($L$) := $\bigcup_{x\in L}$ perm($x$). perm($L$) is niet context-vrij als 104 $L$ de reguliere taal is \{$x \in a^*b^*c^*$ : $|x|_a,|x|_b,|x|_c$ even zijn\}. 56 \section{Opgave 5.8} 105 57 106 [Dit is handen wapperen, ik zou graag wel willen weten hoe dit bewezen107 kan worden] Als $L$ echter een reguliere taal over een alfabet van twee108 symbolen is, dan zal perm($L$) context-vrij zijn. Welke de reguliere taal,109 maximaal \'e\'en complexe relatie kan aangaan en wel namelijk tussen de twee110 symbolen in. Alle andere gevallen (enkel relatie \'e\'en symbool) is er maar111 een enkelvoudige afhankelijk gecodeerd. Pak bijvoorbeeld de ingewikkelde112 \{$x \in a^*b^*$ : $|x|_a,|x|_b$ even zijn\}. De permutatie van bijvoorbeeld113 $aabb$ zullen zijn ${aabb,abba,abab,baba,baab,bbaa}$, waarbij in het114 context-vrije domein een analoge taal ontstaan, waarbij het aantal a `even'115 moet zijn om te accepteren en het aantal b gelijk aan het aantal `a'.116 58 117 \section{Opgave 4.41} 118 Om te bewijzen dat, de taal van alle woorden over de $\{0,1\}$ welke geen 119 prefixen zijn van een Thue-Morse woord context-vrij is, moet er gekeken worden 120 naar het meer generieke geval. Thue-Morse woorden zijn overlap-vrij, een 121 context-vrije taal alle woorden opsomt welke een overlap bevatten is dus 122 voldoende. Woorden met een overlap bevatten de serie $cxcxc$ waarbij $c$ een 123 letter is en $x$ een woord, de overlap is dan $cxc$. De taal van de woorden 124 ziet er dus als volgt uit: $\{0,1\}^*1x1x\{0,1\}^*$ of $\{0,1\}^*0x0x\{0,1\}^*$ 125 waarbij $x := \{0,1\}\{0,1\}^*$. Beiden delen zijn met een (niet 126 deterministische) grammatica te maken, door expansie te doen vanuit `het 127 midden'. Waarbij te denken is aan een soortgelijke setup (a,b ipv 0,1): 128 \begin{verbatim} 129 S -> JMJ 130 J -> aJ|bJ|a|b 131 M -> aOa|bPb 132 O -> aOa|bOb|a 133 P -> aPa|bPb|b 134 \end{verbatim} 59 \section{Opgave 5.14} 135 60 136 61
Note:
See TracChangeset
for help on using the changeset viewer.