Finite-State Methods In Natural Language Processing (600.405) Jason Eisner (jason@cs.jhu.edu) First-Day Questionnaire - Nov. 7, 2000 Name: Email: Status & year: Favorite candy bar: Hobbies: Other identifying features (or self-portrait): Are you in this class for credit, for audit, or in secret? What JHU computer networks do you have accounts on? If you prefer using some networks to others, please also rank them on the dashed lines. [ ] ____ CS research network (peregrine, condor, ...) [ ] ____ CS undergrad network (hops, malt, ...) [ ] ____ CS NLP lab network (bigram, phrase, ...) [ ] ____ CLSP network (speak, dc02, ...) [ ] ____ Other ____________________________________ On a scale of 1-4, how much do you hope to get out of this course in each of the following three areas? 1 2 3 4 (exposure) (comfort) (full or deep (preparation to understanding) extend the work) Theory Applications Software tools On the same scale of 0 to 4, how much do you know (and remember) about each of the following topics? (Don't worry, this info won't be used against you - I'm just trying to find out what the class as a whole knows! :-) ___ determinization of finite-state automata ___ minimization of finite-state automata ___ epsilon-closure (epsilon-removal) in finite-state automata ___ pumping lemma ___ regular expressions (regexps) ___ extensions to regexps (e.g., in Perl): _______________________________ ___ push-down automata ___ context-free parsing ___ undecidable problems for CFGs or PDAs ___ Turing machines ___ closure of a set under given operations ___ group theory ___ ring theory (over, please) ___ rings of polynomials ___ power series (e.g., Taylor series) ___ convergence to a limit ___ measure theory ___ topology (e.g., metric spaces) ___ derivational phonology ___ optimality theory ___ morphology ___ templatic morphology ___ two-level morphology ___ part-of-speech tagging ___ conditional probability ___ Bayes' theorem ___ language modeling ___ simulated annealing ___ gradient descent ___ other optimization techniques: ________________________________________ ___ forward-backward algorithm ___ inside-outside algorithm ___ k-means clustering algorithm ___ expectation-maximization (EM) ___ other unsupervised learning techniques: _______________________________ ___ decision trees ___ decision lists ___ transformation-based learning ("Brill rules") ___ simple Prolog programming What are your main research interests? Have you ever chosen on your own to use finite-state methods? What for? Any other background relevant to this course? Anything else you want to say? Write a regular expression that accepts only binary numbers that are divisible by 4. A binary number is divisible by 3 iff the number of 1's in even positions = the number of 1's in odd positions (mod 3). For example, 1010111 = 87 = 29*3 has four 1's in even positions and one 1 in an odd position. Draw a finite-state machine that accepts only binary numbers that are divisible by 3.