Exam (elaborations) TEST BANK FOR Speech and Language Processing 2nd Edition By Bethard S., Jurafsky D. and Martin J.H. (Instructor's Solution Manual)

I Words 1 2 Regular Expressions and Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 Words and Transducers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4 N-Grams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5 Part-of-Speech Tagging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6 Hidden Markov and Maximum EntropyModels . . . . . . . . . . . . . . . . . . . 27 II Speech 31 7 Phonetics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 8 Speech Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 9 Automatic Speech Recognition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 10 Speech Recognition: Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 11 Computational Phonology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 III Syntax 43 12 Formal Grammars of English. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 13 Syntactic Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 14 Statistical Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 15 Features and Unification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 16 Language and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 IV Semantics and Pragmatics 69 17 The Representation of Meaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 18 Computational Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 19 Lexical Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 20 Computational Lexical Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 21 Computational Discourse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 V Applications 93 22 Information Extraction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 23 Question Answering and Summarization . . . . . . . . . . . . . . . . . . . . . . . . . . 100 24 Dialogue and Conversational Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 25 Machine Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 i Chapter 2 Regular Expressions and Automata 2.1 Write regular expressions for the following languages. You may use either Perl/Python notation or the minimal “algebraic” notation of Section 2.3, but make sure to say which one you are using. By “word”, we mean an alphabetic string separated from other words by whitespace, any relevant punctuation, line breaks, and so forth. 1. the set of all alphabetic strings; [a-zA-Z]+ 2. the set of all lower case alphabetic strings ending in a b; [a-z]*b 3. the set of all strings with two consecutive repeated words (e.g., “Humbert Humbert” and “the the” but not “the bug” or “the big bug”); ([a-zA-Z]+)s+1 4. the set of all strings from the alphabet a, b such that each a is immediately preceded by and immediately followed by a b; (b+(ab+)+)? 5. all strings that start at the beginning of the line with an integer and that end at the end of the line with a word; ˆd+b.*b[a-zA-Z]+$ 6. all strings that have both the word grotto and the word raven in them (but not, e.g., words like grottos that merely contain the word grotto); bgrottob.*bravenb|bravenb.*bgrottob 7. write a pattern that places the first word of an English sentence in a register. Deal with punctuation. ˆ[ˆa-zA-Z]*([a-zA-Z]+) 2.2 Implement an ELIZA-like program, using substitutions such as those described on page 26. You may choose a different domain than a Rogerian psychologist, if you wish, although keep in mind that you would need a domain in which your program can legitimately engage in a lot of simple repetition. The following implementation can reproduce the dialog on page 26. A more complete solution would include additional patterns. import re, string patterns = [ (r"b(i’m|i am)b", "YOU ARE"), (r"b(i|me)b", "YOU"), (r"b(my)b", "YOUR"), (r"b(well,?) ", ""), (r".* YOU ARE (depressed|sad) .*", r"I AM SORRY TO HEAR YOU ARE 1"), (r".* YOU ARE (depressed|sad) .*", r"WHY DO YOU THINK YOU ARE 1"), 1 2 Chapter 2. Regular Expressions and Automata (r".* all .*", "IN WHAT WAY"), (r".* always .*", "CAN YOU THINK OF A SPECIFIC EXAMPLE"), (r"[%s]" % e(uation), ""), ] while True: comment = raw_input() response = () for pat, sub in patterns: response = (pat, sub, response) print () 2.3 Complete the FSA for Englishmoney expressions in Fig. 2.15 as suggested in the text following the figure. You should handle amounts up to $100,000, and make sure that “cent” and “dollar” have the proper plural endings when appropriate. 2.4 Design an FSA that recognizes simple date expressions like March 15, the 22nd of November, Christmas. You should try to include all such “absolute” dates (e.g., not “deictic” ones relative to the current day, like the day before yesterday). Each edge of the graph should have a word or a set of words on it. You should use some sort of shorthand for classes of words to avoid drawing too many arcs (e.g., furniture! desk, chair, table). 3 2.5 Now extend your date FSA to handle deictic expressions like yesterday, tomorrow, a week from tomorrow, the day before yesterday, Sunday, next Monday, three weeks from Saturday. 2.6 Write an FSA for time-of-day expressions like eleven o’clock, twelve-thirty, midnight, or a quarter to ten, and others. 2.7 (Thanks to Pauline Welby; this problem probably requires the ability to knit.) Write a regular expression (or draw an FSA) that matches all knitting patterns for scarves with the following specification: 32 stitches wide, K1P1 ribbing on both ends, stockinette stitch body, exactly two raised stripes. All knitting patterns must include a cast-on row (to put the correct number of stitches on the needle) and a bind-off row (to end the pattern and prevent unraveling). Here’s a sample pattern for one possible scarf matching the above description:1 1 Knit and purl are two different types of stitches. The notation Kn means do n knit stitches. Similarly for purl stitches. Ribbing has a striped texture—most sweaters have ribbing at the sleeves, bottom, and neck. Stockinette stitch is a series of knit and purl rows that produces a plain pattern—socks or stockings are knit with this basic pattern, hence the name. 4 Chapter 2. Regular Expressions and Automata 1. Cast on 32 stitches. cast on; puts stitches on needle 2. K1 P1 across row (i.e., do (K1 P1) 16 times). K1P1 ribbing 3. Repeat instruction 2 seven more times. adds length 4. K32, P32. stockinette stitch 5. Repeat instruction 4 an additional 13 times. adds length 6. P32, P32. raised stripe stitch 7. K32, P32. stockinette stitch 8. Repeat instruction 7 an additional 251 times. adds length 9. P32, P32. raised stripe stitch 10. K32, P32. stockinette stitch 11. Repeat instruction 10 an additional 13 times. adds length 12. K1 P1 across row. K1P1 ribbing 13. Repeat instruction 12 an additional 7 times. adds length 14. Bind off 32 stitches. binds off row: ends pattern In the expression below, C stands for cast on, K stands for knit, P stands for purl and B stands for bind off: C{32} ((KP){16})+ (K{32}P{32})+ P{32}P{32} (K{32}P{32})+ P{32}P{32} (K{32}P{32})+ ((KP){16})+ B{32} 2.8 Write a regular expression for the language accepted by the NFSA in Fig. 2.26. q q3 0 q1 q2 a b a b a Figure 2.1 A mystery language. (aba?)+ 2.9 Currently the function D-RECOGNIZE in Fig. 2.12 solves only a subpart of the important problem of finding a string in some text. Extend the algorithm to solve the following two deficiencies: (1) D-RECOGNIZE currently assumes that it is already pointing at the string to be checked, and (2) D-RECOGNIZE fails if the string it is pointing to includes as a proper substring a legal string for the FSA. That is, D-RECOGNIZE fails if there is an extra character at the end of the string. To address these problems, we will have to try to match our FSA at each point in the tape, and we will have to accept (the current substring) any time we reach an accept state. The former requires an 5 additional outer loop, and the latter requires a slightly different structure for our case statements: function D-RECOGNIZE(tape,machine) returns accept or reject current-state Initial state of machine for index from 0 to LENGTH(tape) do current-state Initial state of machine while index < LENGTH(tape) and transition-table[current-state,tape[index]] is not empty do current-state transition-table[current-state,tape[index]] index index + 1 if current-state is an accept state then return accept index index + 1 return reject 2.10 Give an algorithm for negating a deterministic FSA. The negation of an FSA accepts exactly the set of strings that the original FSA rejects (over the same alphabet) and rejects all the strings that the original FSA accepts. First, make sure that all states in the FSA have outward transitions for all characters in the alphabet. If any transitions are missing, introduce a new non-accepting state (the fail state), and add all the missing transitions, pointing them to the new non-accepting state. Finally, make all non-accepting states into accepting states, and vice-versa. 2.11 Why doesn’t your previous algorithm work with NFSAs? Now extend your algorithm to negate an NFSA. The problem arises from the different definition of accept and reject in NFSA. We accept if there is “some” path, and only reject if all paths fail. So a tape leading to a single reject path does neccessarily get rejected, and so in the negated machine does not necessarily get accepted. For example, we might have an -transition from the accept state to a non-accepting state. Using the negation algorithm above, we swap accepting and non-accepting states. But we can still accept strings from the original NFSA by simply following the transitions as before to the original accept state. Though it is now a non-accepting state, we can simply follow the -transition and stop. Since the - transition consumes no characters, we have reached an accepting state with the same string as we would have using the original NFSA. To solve this problem, we first convert the NFSA to a DFSA, and then apply the algorithm as before. Chapter