Существует алгоритм, который делает именно это для положительных примеров.
Регулярные выражения эквивалентны DFA (Детерминированные конечные автоматы).
Стратегия в основном всегда одна и та же:
Посмотрите на Alergia (для теории) и алгоритм MDI (для реального использования), если генерации детерминированного автомата достаточно.
Алгоритм аллергии и MDI описаны здесь:
http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/icml2k.pdf
Если вы хотите создавать меньшие модели, вы можете использовать другой алгоритм. Статья, описывающая это здесь:
http://www.grappa.univ -lille3.fr / ~ ЛеМэй / це / TCS02.ps.gz
Его домашняя страница здесь:
http://www.grappa.univ -lille3.fr / ~ ЛеМэй
Если вы хотите использовать отрицательный пример, я предлагаю вам использовать простое правило (раскраска), которое предотвращает слияние двух состояний DFA.
Если вы спросите этих людей, я уверен, что они поделятся своим источником кода.
Я сделал такой же алгоритм во время моей кандидатской диссертации. для вероятностных автоматов. Это означает, что вы можете связать вероятность с каждой строкой, и я создал программу на C ++, которая «изучает» взвешенные автоматы.
В основном эти алгоритмы работают так:
из положительных примеров: {abb, aba, abbb}
создайте простейший DFA, который принимает все эти примеры:
-> x -- a --> (y) -- b --> (z)
\
b --> t -- b --> (v)
x не могу указать y, прочитав, например, букву «а».
Состояния x, y, z, t и v. (Z) означает, что это конечное состояние.
затем «объединить» состояния DFA: (здесь, например, результат после объединения состояний y и t.
_
/ \
v | a,b ( <- this is a loop :-) )
x -- a -> (y,t) _/
новое состояние (y, t) - это состояние терминала, полученное путем слияния y и t. И вы можете прочитать письмо а и б из него.
Теперь DFA может принимать: a (a | b) *, и регулярное выражение легко построить из DFA.
Какие состояния для слияния - это выбор, который делает основное различие между алгоритмами.