Assignment One

    Assignment One is due Tues., Jan. 30.


    1. Write regexes for the sets of atrings 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 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:

    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.