A. Textbook
Problems
|
|
- Write regexes for the sets of strings below:
- all alphabetic strings
- all lower case alphabetic strings ending in d
- 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).
- all strings from the alphabet 0, 1 such that each 0 is immediately
preceded by and immediately followed by a 1.
- 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.
- 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.
- Write a regular expression for the language accepted by the
following FSA:
|
|
Contd.
|
|
|
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.
|
|
