Test intersezione di due lingue regolari

Voglio verificare se due lingue hanno una stringa in comune. Entrambe queste lingue provengono da un sottogruppo di linguaggi regolari descritto di seguito e ho solo bisogno di sapere se esiste una stringa in entrambe le lingue, non produrre una stringa di esempio.Test intersezione di due lingue regolari

La lingua è specificato da una stringa glob-come come

/foo/**/bar/*.baz

dove ** partite 0 o più caratteri, e * partite zero o più caratteri che non sono /, e tutti altri personaggi sono letterali.

Qualche idea?

grazie, Mike

EDIT:

ho implementato qualcosa che sembra funzionare bene, ma devono ancora provare una prova di correttezza. Potete vedere il source e unit tests

fonte

2010-02-26 Mike Samuel

Quale lingua utilizzerai per eseguire il controllo? Probabilmente avrai bisogno di scrivere un banco di prova per questo. Se potessi pubblicare un banco di prova abbastanza completo sarebbe di aiuto. –

Questo dovrà essere eseguito in JS. Ovviamente dovrò scrivere un banco di prova. Ho trovato un sottoinsieme utile per il quale posso calcolare l'intersezione in modo efficiente facendo alcuni trucchi. Il sottoinsieme utile è uno dove * e ** possono apparire solo all'inizio o direttamente dopo un /, e un/non può essere adiacente ad un altro /. Ciò significa che non ho mai bisogno di preoccuparmi se * foo * può corrispondere a boo * baz - Devo fare il backtracking, ma non una quantità ridicola dato che posso sempre trasformare il testo dopo un * o ** in un controllo suffisso. –

Corporatura FAs A e B per entrambe le lingue, e costruire il "intersezione FA" AnB. Se AnB ha almeno uno stato di accettazione accessibile dallo stato di avvio, allora c'è una parola che è in entrambe le lingue.

La costruzione di AnB potrebbe essere complicato, ma sono sicuro che ci sono libri di testo di FA che lo coprono. L'approccio Vorrei prendere è:

Gli stati di AnB è, rispettivamente, il prodotto cartesiano degli stati di A e B. Uno stato in AnB è scritto (a, b) dove a è uno stato in A e b è uno stato in B.
Una transizione (a, b) ->r (c, d) (significato, c'è una transizione da (a, b) a (c, d) sul simbolo r) esiste sse a ->r c è una transizione in A e b ->r d è una transizione in B.
(a, b) è uno stato di avvio in AnB sse a e b sono stati iniziare a A e B rispettivamente.
(a, b) è uno stato di accettazione in AnB se ciascuno è uno stato accettante nel rispettivo FA.

Questo è tutto in cima alla mia testa, e quindi completamente non provata!

fonte

2010-02-26 01:32:28 Edmund

Bene, questa è una ben documentata costruzione chiamata Cartesian Product Machine, molte persone vi hanno battuto per questo, ed è un metodo ben documentato e corretto per far riconoscere ad una FA l'intersezione di lingue riconosciute da altri FA. Sto solo dicendo – Patrick87

Ho appena fatto una ricerca rapida e questo problema è decidibile (anche noto), ma non conosco alcun buon algoritmo per farlo. Uno è soluzione è:

convertire sia regolari espressioni per NFA A e B
Creare un NFA, C, che rappresenta l'intersezione di A e B.
Ora prova ogni stringa da 0 al numero di stati in C e controlla se C lo accetta (poiché se la stringa è più lunga deve ripetere gli stati in un punto).

So che potrebbe essere un po 'difficile da seguire, ma questo è solo il modo in cui so come.

fonte

2010-02-26 02:00:43 Bishnu

Test intersezione di due lingue regolari

risposta

Problemi correlati