Exercises
Exercises
dub+Te dubde wend+Te wendde bof+Te bofte leeg+Te leegde kuch+Te kuchte push+Te pushte gooi+Te gooide roetsj+Te roetsjte buk+Te bukte ril+Te rilde ram+Te ramde ren+Te rende rep+Te repte hoor+Te hoorde pas+Te paste zet+Te zette leev+Te leefde geeuw+Te geeuwde fax+Te faxte soez+Te soesde
macro(swap,[{a,b}*,a:b,b:a,{a,b}*]).This swaps a pair of a,b to b,a, while copying the rest of the string (which also contains a's and b's). Let us write tr_cl_swap for the transitive closure of swap, wrt composition, i.e., swap o swap o swap o .... o swap. Consider the language
[a,b]* o tr_cl_swapFurthermore, consider the intersection of this language, with the language
[b*,a*]Describe this language. Why does this show that tr_cl_swap is not a regular relation?
related chapters in the book: edition2: [ch 3; ch 4; ch 11]
The suffix arrays implementation (with perfect hash keys for words) is available from www.let.rug.nl/~vannoord/software.html
Exercises
A Perl script to compute word Ngram frequencies is available as make_ngram. You can use this for the next exercises.
If you work on the LWP, you don't need to install the software, but you can use it directly at /net/aps/64/src/Alpino/SuffixArrays/. In order to use the binary, you may need to set
export LD_LIBRARY_PATH=/net/aps/64/lib
My solution:
% cd /net/aps/64/src/Alpino/SuffixArrays/Examples % head nlwiki-20110804.txt @ Albert Speer . @ Berthold Konrad Hermann Albert Speer ( Mannheim , 19 maart 1905 -- Londen , 1 september 1981 @ Hij raakte , onder andere vanwege hun gemeenschappelijke belangstelling voor architectuur , @ Speer wordt wel de ' architect van het Derde Rijk ' genoemd en hij was één van de kopstukken @ Hij had zes kinderen , van wie er één , Albert Speer jr. @ ( geboren in 1934 ) , na de oorlog eveneens een bekend architect is geworden . @ Voor 1933 . @ Het gezin waarin Albert Speer werd geboren , was wat ze in het Duits noemen ' grossbürgerlic @ Zijn vader en grootvader waren beiden architecten . @ Om financiële redenen studeerde Speer aanvankelijk in Karlsruhe . % make nlwiki-20110804.fsa ... % make nlwiki-20110804.ngram ... % head nlwiki-20110804.ngram 1|!|14608 1|!!|167 1|!!!|127 1|!!!!|11 1|!!!.|17 1|!!.|19 1|!!?|10 1|!.|442 1|!...|44 1|!?|52 % grep '^12|' nlwiki-20110804.ngram |head 12|! @ @ ! @ @ ! @ Intertoto Cup @ !|17 12|! @ @ ! @ Intertoto Cup @ ! @ Intertoto Cup|17 12|! @ Christus vincit ! @ Christus regnat ! @ Christus imperat|6 12|! @ De reeks wordt getekend door striptekenaarsduo Wim Swerts & Vanas|6 12|! @ Gimme ! @ Gimme ! @ ( A Man After|7 12|!!? , The @ Incredibly Strange Creatures Who Stopped Living and Became|6 12|!. @ De reeks wordt getekend door striptekenaarsduo Wim Swerts & Vanas|6 12|" " Cat : " staat voor catalogusnummer van de maatschappij ;|9 12|" $10.000 No Limit Hold'em - Championship Event " van de "|6 12|" $5.000 No Limit Deuce to Seven Draw"-toernooi van de World Series|6 % awk -F\| '/^12[|]/{if ($3 > MAX) {MAX=$3;MAXL=$2}} END {print MAX,MAXL}' nlwiki-20110804.ngram 35667 . @ Demografie . @ Onderstaande figuur toont het verloop van het % grep -v @ nlwiki-20110804.ngram | awk -F\| '/^12[|]/{if ($3 > MAX) {MAX=$3;MAXL=$2}} END {print MAX,MAXL}' 31502 toont het verloop van het inwonertal ( bron : INSEE-tellingen ) .
Alternatief met Perl-script:
cat nlwiki.txt |\ tr -s '\012\011 ' '\012' |\ ../make_ngram -n 12 |\ grep -v '@' |\ sort -nr -k 13
Exercises
P(D|start) = 0.1 P(N|start) = 0.4 P(V|start) = 0.2 P(PRON|start) = 0.1 P(het|D) = 0.25 P(het|PRON) = 0.05 P(was|N) = 0.0001 P(was|V) = 0.01 P(slapen|V) = 0.0001 P(slapen|N) = 0.0001 P(V|D) = 0.00001 P(N|D) = 0.4 P(V|PRON) = 0.05 P(N|PRON) = 0.001 P(D|V) = 0.01 P(PRON|V) = 0.01 P(PRON|N) = 0.001 P(D|N) = 0.001 P(end|D) = 0.25 P(end|PRON) = 0.25 P(end|N) = 0.25 P(end|V) = 0.25
Exercises
Exercises