Existe un algoritmo que hace exactamente esto para ejemplos positivos.
La expresión regular es equivalente a DFA (autómatas finitos deterministas). La estrategia es siempre la misma:
Mire Alergia (por la teoría) y el algoritmo MDI (para uso real) si generar un Autómata determinista es suficiente.
algoritmo de la Alergia y MDI son ambos describen a continuación: http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/icml2k.pdf
Si desea generar modelos más pequeños se pueden utilizar otro algoritmo. El artículo que describe es aquí: http://www.grappa.univ-lille3.fr/~lemay/publi/TCS02.ps.gz
Su página está aquí: http://www.grappa.univ-lille3.fr/~lemay
Si desea utilizar ejemplo negativo, sugiero que utilice una regla simple (colorante) que impiden que dos estados de la DFA fusionarse
Si le preguntas a estas personas, estoy seguro de que compartirán su código fuente.
Hice el mismo tipo de algoritmo durante mi Ph.D. para autómatas probabilísticos. Eso significa que puede asociar una probabilidad a cada cadena, y he creado un programa C++ que "aprende" autómatas ponderados.
Principalmente estos trabajos algoritmo de esa manera:
a partir de ejemplos positivos: {ABB, aba, ABBB}
crear la DFA más simple que acepte exactamente todos estos ejemplos:
-> x -- a --> (y) -- b --> (z)
\
b --> t -- b --> (v)
x cativas tiene que declarar y leyendo la letra 'a' por ejemplo. Los estados son x, y, z, t y v. (Z) significa que es un estado finito.
entonces estados "de combinación" de la DFA:. (Aquí por ejemplo el resultado después de la fusión de los estados y y t
_
/\
v | a,b (<- this is a loop :-))
x -- a -> (y,t) _/
el nuevo estado (y, t) es un estado terminal de la obtención mediante la fusión de Y y t. Y puede leer la letra a y b de la misma. Ahora el DFA puede aceptar: a (a | b) * y es fácil construir la expresión regular del DFA.
Qué estados fusionar es una elección que hace la diferencia principal entre los algoritmos.
XD. Solo tengo en mente que el usuario ingrese entradas aceptadas como "Debe coincidir con 'bob', 'charlie' y 'grant'", y el generador de expresiones regulares escupiendo "REGEXP = bob | charlie | grant". > _>. – Stephen
@Stephen esa es mi preocupación, así, es por eso que estoy buscando de entrada: P –
Tal vez un algoritmo genético podría dar puntos para las expresiones más cortas ... –