Regex Edit Distance

The general idea here is that you can calculate not only whether or not a string matches a regex, but if it doesn't match, precisely by how much (in the minimal case).