A. Textbook Problems 1. Write regexes for the sets of strings below: 1. all alphabetic strings 2. all lower case alphabetic strings ending in d 3. all strings with two consecutive repeated words, for example, very very or the the but not the big bang (two consecutive non-identical words starting and ending with the same letter) or a picture of a car (two occurrences of the word a but not consecutive occurrences). 4. all strings from the alphabet 0, 1 such that each 0 is immediately preceded by and immediately followed by a 1. 5. all strings that have both the words charge and call in either order and not necessarily consecutive, but not words like charged or calls that merely contain the words we're looking for. 2. Draw a state diagram for an FSA that recognizes money amounts using the alphabet $,0123456789. Note the occurrences of "." and "," in the alphabet. The FSA should recognize any amount of money, no matter how large, for example $1, $3.14, $1,000.00, $1000 and $1,456,412.31, but it should fail on 3.14, $3.145, $1,5643,452.12. 3. Write a regular expression for the language accepted by the following FSA: b 90 91 43 b B. Min Edit distance A. Compute the edit distance (using Levenshtein distance) of "leda" to "deal. Show your work. You must use the minimum edit distance algorithm (which involves showing your work on the minimum edit distance grid). B. Figure out whether "drive" is closer to "brief" or to "divers" and what the edit distance is to each. Use Levenshtein distance. A. Textbook Problems 1. Write regexes for the sets of strings below: 1. all alphabetic strings 2. all lower case alphabetic strings ending in d 3. all strings with two consecutive repeated words, for example, very very or the the but not the big bang (two consecutive non-identical words starting and ending with the same letter) or a picture of a car (two occurrences of the word a but not consecutive occurrences). 4. all strings from the alphabet 0, 1 such that each 0 is immediately preceded by and immediately followed by a 1. 5. all strings that have both the words charge and call in either order and not necessarily consecutive, but not words like charged or calls that merely contain the words we're looking for. 2. Draw a state diagram for an FSA that recognizes money amounts using the alphabet $,0123456789. Note the occurrences of "." and "," in the alphabet. The FSA should recognize any amount of money, no matter how large, for example $1, $3.14, $1,000.00, $1000 and $1,456,412.31, but it should fail on 3.14, $3.145, $1,5643,452.12. 3. Write a regular expression for the language accepted by the following FSA: b 90 91 43 b B. Min Edit distance A. Compute the edit distance (using Levenshtein distance) of "leda" to "deal. Show your work. You must use the minimum edit distance algorithm (which involves showing your work on the minimum edit distance grid). B. Figure out whether "drive" is closer to "brief" or to "divers" and what the edit distance is to each. Use Levenshtein distance
