Войти
В теории вычислительного обучения, введение в регулярные языки относится к задача изучения формального описания (например, грамматика) обычного языка из заданного набора примеров строк. Хотя Марк Э. Голд показал, что не каждый регулярный язык можно выучить таким образом (см. идентификация языка в пределе ), подходы были исследованы для множества подклассов. Они обрисованы в общих чертах в этой статье. Для изучения более общих грамматик см. Введение в грамматику.
A регулярный язык определяется как (конечный или бесконечный) набор строк, который может быть описан одним из математических формализмов под названием «конечный автомат "," регулярная грамматика "или" регулярное выражение ", все из которых имеют одинаковую выразительную силу. Поскольку последний формализм приводит к кратчайшим обозначениям, он будет введен и использован здесь. Учитывая набор Σ символов (он же алфавит), регулярное выражение может быть любым из
Например, используя Σ = {0,1}, регулярное выражение (0 + 1 + ε) ⋅ (0 + 1) обозначает набор все двоичные числа с одной или двумя цифрами (разрешены ведущие нули), а 1⋅ (0 + 1) ⋅0 обозначает (бесконечный) набор всех четных двоичных чисел (без ведущих нулей).
Учитывая набор строк (также называемых «положительными примерами»), задача индукции регулярного языка состоит в том, чтобы придумать регулярное выражение, которое обозначает набор, содержащий их все. В качестве примера, учитывая {1, 10, 100}, «естественным» описанием может быть регулярное выражение 1⋅0, соответствующее неформальной характеристике «1, за которой следует произвольное количество (возможно, даже ни одного) 0». Однако (0 + 1) и 1+ (1⋅0) + (1⋅0⋅0) - это другое регулярное выражение, обозначающее наибольшее (при условии, что Σ = {0,1}) и наименьшее множество, содержащее заданные строки, и называется тривиальным сверхобобщением и недостаточным обобщением соответственно. Некоторые подходы работают в расширенной настройке, где также приводится набор строк «отрицательного примера»; тогда нужно найти регулярное выражение, которое генерирует все положительные, но ни один из отрицательных примеров.
 Частичный порядок автоматов, порождающих строки 1, 10 и 100 (положительные примеры). Для каждой из отрицательных примерных строк 11, 1001, 101 и 0 показан верхний набор автоматов, генерирующих его. Единственные автоматы, которые генерируют все {1, 10, 100}, но ни один из {11, 1001, 101, 0}, - это тривиальный нижний автомат и тот, который соответствует регулярному выражению 1⋅0. |
Dupont et al.. показали, что набор всех структурно полных конечных автоматов, генерирующих данный входной набор примеров строк, образует решетку, с тривиальным неполнообобщенным и тривиальным сверхобобщенным автоматом в качестве нижнего и верхнего элементов соответственно. Каждый член этой решетки может быть получен путем факторизации недостаточно обобщенного автомата с помощью соответствующего отношения эквивалентности .
. Для приведенного выше примера набора строк {1, 10, 100} изображение показано внизу. неполнообобщенный автомат A a, b, c, d серым цветом, состоящий из состояний a, b, c и d. На множестве состояний {a, b, c, d} существует всего 15 отношений эквивалентности, образующих решетку. Отображение каждой эквивалентности E на соответствующий язык фактор-автоматов L (Aa, b, c, d / E) дает частично упорядоченный набор, показанный на рисунке. Язык каждого узла обозначается регулярным выражением. Язык может быть распознан с помощью частных автоматов по различные отношения эквивалентности, все из которых показаны под узлом. Стрелка между двумя узлами указывает, что язык нижнего узла является правильным подмножеством языка более высокого узла.
Если даны как положительные, так и отрицательные примеры строк, Dupont et al. Постройте решетку из положительных примеров, а затем исследуйте границу разделения между автоматами, которые генерируют какой-то отрицательный пример, и такими, которые нет. Наиболее интересны те автоматы, которые находятся непосредственно под границей. На рисунке границы разделения показаны для отрицательных примеров строк 11 (зеленый), 1001 (синий), 101 (голубой) и 0 (красный).
Кост и Николас представляют собственный метод поиска в решетке, который они относятся к парадигме Митчелла пространство версий. Чтобы найти границу разделения, они используют алгоритм раскраски графа для отношения неравенства состояний, вызванного отрицательными примерами. Позже они исследуют несколько отношений упорядочения на множестве всех возможных слияний состояний.
Кудо и Шимбо используют представление с помощью автоматных факторизаций, чтобы дать уникальную основу для следующих подходов (набросано ниже) :
Показано, что каждый из этих подходов соответствует определенному типу отношений эквивалентности, используемых для факторизации.
Англуин рассматривает так называемые «k-обратимые» регулярные автоматы, то есть детерминированные автоматы, в которых каждое состояние может быть достигнуто не более чем из одного состояния, следуя цепочке переходов длины k. Формально, если Σ, Q и δ обозначают входной алфавит, набор состояний и функцию переходов автомата A соответственно, то A называется k-обратимым, если: ∀a 0,..., a k ∈ Σ ∀s 1, s 2 ∈ Q: δ (s 1,a0... a k) = δ (s 2,a0... a k) ⇒ s 1 = s 2, где δ означает гомоморфное расширение δ на произвольные слова. Angluin дает кубический алгоритм для изучения наименьшего k-обратимого языка из заданного набора входных слов; при k = 0 алгоритм имеет даже почти линейную сложность. Требуемая уникальность состояния после k + 1 заданных символов вынуждает объединять состояния автомата, таким образом приводя к собственному обобщению, отличному от тривиального недостаточно обобщенного автомата. Этот алгоритм использовался для изучения простых частей синтаксиса английского языка; позже была предоставлена инкрементная версия. Другой подход, основанный на k-обратимых автоматах, - это метод кластеризации хвоста.
Из заданного набора входных строк Вернадат и Рикетен создают так называемый автомат-преемник, состоящий из одного состояния для каждого отдельного символа и перехода между состояниями каждых двух соседних символов. Например, одноэлементный входной набор {aabbaabb} приводит к автомату, соответствующему регулярному выражению (a⋅b).
Расширением этого подхода является метод предшественник-преемник, который немедленно обобщает каждое повторение символа на Kleene, а затем включает для каждого символа набор его возможных предшественников. в его состоянии. Автоматы-последователи могут выучить именно класс местных языков. Поскольку каждый регулярный язык является гомоморфным образом локального языка, грамматики из первого класса могут быть изучены путем подъема, если предусмотрен соответствующий (в зависимости от предполагаемого применения) гомоморфизм. В частности, такой гомоморфизм существует для класса языков, изучаемых методом предшественник-преемник. Изучаемость местных языков может быть сведена к изучению k-обратимых языков.
 Производная Бжозовского (на красном фоне) словарной строки, заданной относительно «con» |
 Иллюстрация леммы о накачке для обычных автоматов |
Хомский и Миллер (1957) использовали лемму о перекачке : они угадывают часть v входной строки uvw и пытаются встроить соответствующий цикл в автомат, который нужно изучить; используя запросы членства, они спрашивают, для соответствующего k, какая из строк uw, uvvw, uvvvw,..., uvw также принадлежит языку, который нужно изучить, тем самым уточняя структуру своего автомата. В 1959 году Соломонов обобщил этот подход на контекстно-свободные языки, которые также подчиняются лемме о накачке.
Кампеану и др. изучать конечный автомат как компактное представление большого конечного языка. Для такого языка F они ищут так называемый покрывающий автомат A такой, что его язык L (A) покрывает F в следующем смысле: L (A) ∩ Σ = F, где l - длина самой длинной строки в F, а Σ обозначает множество всех строк не длиннее l. Если такой автомат покрытия существует, то F однозначно определяется A и l. Например, F = {ad, read, reread} имеет l = 6 и автомат обложки, соответствующий регулярному выражению (r⋅e) ⋅a⋅d.
Для двух строк x и y Кампеану и др. определим x ~ y, если xz∈F ⇔ yz∈F для всех строк z такой длины, что и xz, и yz не длиннее l. Основываясь на этом соотношении, отсутствие транзитивности которого вызывает значительные технические проблемы, они дают алгоритм O (n) для построения из F покрывающего автомата A с минимальным числом состояний. Более того, для объединения, пересечения и разности двух конечных языков они обеспечивают соответствующие операции над их автоматами покрытия. Păun et al. улучшить временную сложность до O (n).
Для набора S строк и строки u, производная Бжозовского uS определяется как множество всех остальных строк, которые можно получить из строки в S путем обрезания префикса u (если возможно), формально: uS = {v ∈ Σ: uv ∈ S}, ср. картина. Денис и др. Определим остаточный автомат как недетерминированный конечный автомат A, где каждое состояние q соответствует производной Бжозовского принятого языка L (A), формально: ∀q∈Q ∃u∈Σ: L (A, q) = uL (A), где L (A, q) обозначает язык, принятый из q в качестве начального состояния.
Они показывают, что каждый регулярный язык порождается однозначно определенным минимальным остаточным автоматом. Его состояния являются ∪-неразложимыми производными Бжозовского, и он может быть экспоненциально меньше, чем минимальный детерминированный автомат. Более того, они показывают, что остаточные автоматы для обычных языков нельзя выучить за полиномиальное время, даже при условии оптимальных исходных данных. Они дают алгоритм обучения для остаточных автоматов и доказывают, что он изучает автомат по его характерному образцу положительных и отрицательных входных строк.
.
Обычные языки не могут быть изучены за полиномиальное время, используя только запросы членства или используя только запросы эквивалентности. Однако Angluin показал, что обычные языки можно выучить за полиномиальное время, используя запросы членства и запросы эквивалентности, и предоставил алгоритм обучения, названный L *, который делает именно это. Позднее алгоритм L * был обобщен для вывода NFA (недетерминированных конечных автоматов ), а не DFA (детерминированных конечных автоматов ), посредством алгоритма, названного NL *. Этот результат был дополнительно обобщен, и был разработан алгоритм, который выводит AFA (чередующиеся конечные автоматы ), названный AL *. Следует отметить, что NFA могут быть экспоненциально более лаконичными, чем DFA, и что AFA могут быть экспоненциально более лаконичными, чем NFA, и вдвойне экспоненциально более лаконичными, чем DFA.
Брилл определяет сокращенное регулярное выражение как любое из
Учитывая входной набор строк, он шаг за шагом строит дерево с каждой ветвью, помеченной сокращенным регулярным выражением, принимающим префикс некоторых входных строк, и каждым узлом, помеченным набором длин принятых префиксов. Он нацелен на изучение правил исправления орфографических ошибок английского языка, а не на теоретические соображения об усваиваемости языковых классов. Следовательно, он использует эвристику, чтобы сократить древовидную структуру, что приводит к значительному сокращению времени выполнения.
