Edit distance between two regular expression

Question

I faced this question in an interview:

Given two regular expression, compute the edit distance between them. The edit distance being defined as the smallest edit distance between any two strings generated by the two regular expressions respectively.

Formally, we are looking for d(L1,L2) = min { d(x,y) | x from L1, y from L2 }, where L1 and L2 are the languages generated by the two regular expressions.

I was not able to solve it during interviews. Even now I don't have any clue how to solve it. Any ideas?

I think this is same as http://www.spoj.com/problems/AMR10B/

Answer 1

There's finite state machines that represent the two languages. Let's say the first language has states S[1], S[2], ..., S[N1] and transitions c: S[i]->S[j] (meaning state i goes to state j under input character c), and T[1], T[2], ... T[N2] for the second language (with its own set of transitions).

Now, you can construct the weighted multi-graph with nodes being pairs of states, and edges between pairs (S[i1], T[i2]) -> (S[j1], T[j2]) if any of these four cases hold:

• There's c: S[i1] -> S[j1] and i2 = j2. This has weight 1
• There's c: T[i2] -> T[j2] and i1 = j1. This has weight 1
• There's c: S[i1] -> S[j1] and c: T[i2] -> T[j2]. This has weight 0
• There's c: S[i1] -> S[j1] and d: T[i2] -> T[j2]. This has weight 1

Then, finding the lowest weight path from the pair of start states to any pair of accepting states gives you the minimal edit distance.