Modifica la distanza tra due espressioni regolari

Question

Ho affrontato questa domanda in un'intervista:

Data due espressioni regolari, calcolare la distanza di modifica tra di loro. La distanza di modifica viene definita come la minima distanza di modifica tra due stringhe generate rispettivamente dalle due espressioni regolari.

Formalmente, stiamo cercando d(L1,L2) = min { d(x,y) | x from L1, y from L2 }, dove L1 e L2 sono le lingue generate dalle due espressioni regolari.

Non sono stato in grado di risolverlo durante le interviste. Anche adesso non ho idea di come risolverlo. Qualche idea?

penso che questo è lo stesso come http://www.spoj.com/problems/AMR10B/

Answer 1

C'è macchine a stati finiti che rappresentano le due lingue. Diciamo che la prima lingua ha stati S [1], S [2], ..., S [N1] e transizioni c: S [i] -> S [j] (che significa che lo stato i va a stato j sotto carattere di input c), e T [1], T [2], ... T [N2] per la seconda lingua (con il proprio insieme di transizioni).

Ora, è possibile costruire il multi-grafico ponderato con nodi di coppie di stati e bordi tra coppie (S [i1], T [i2]) -> (S [j1], T [j2]) se uno di questi quattro casi contiene:

• C'è c: S [i1] -> S [j1] e i2 = j2. Questo ha il peso 1
• C'è c: T [i2] -> T [j2] e i1 = j1. Questo ha il peso 1
• C'è c: S [i1] -> S [j1] ec: T [i2] -> T [j2]. Questo ha il peso 0
• C'è c: S [i1] -> S [j1] e d: T [i2] -> T [j2]. Questo ha il peso 1

Quindi, trovare il percorso di peso più basso dalla coppia di stati di avvio a qualsiasi coppia di stati di accettazione fornisce la distanza di modifica minima.