✖


Jump to content

Индукция регулярных языков

В компьютерного обучения теории индукция регулярных языков относится к задаче изучения формального описания (например, грамматики) регулярного языка на основе заданного набора примеров строк. Хотя Э. Марк Голд показал, что не каждый обычный язык можно выучить таким способом (см. определение языка в пределе ), подходы исследовались для множества подклассов. Их эскизы представлены в этой статье. Для изучения более общих грамматик см. «Введение в грамматику» .

Определения [ править ]

Регулярный язык определяется как (конечный или бесконечный) набор строк , который может быть описан одним из математических формализмов, называемых « конечный автомат », « регулярная грамматика » или « регулярное выражение », каждый из которых имеет одинаковую выразительную силу. . Поскольку последний формализм приводит к кратчайшим обозначениям, он будет введен и использован здесь. Учитывая набор символов Σ (также известный как алфавит), регулярное выражение может быть любым из

  • ∅ (обозначающий пустой набор строк),
  • ε (обозначает одноэлементный набор, содержащий только пустую строку),
  • a (где a — любой символ из Σ; обозначает одноэлементный набор, содержащий только односимвольную строку a ),
  • r + s (где r и s , в свою очередь, являются более простыми регулярными выражениями; обозначают объединение их множества)
  • r ⋅ s (обозначает набор всех возможных конкатенаций строк из набора r и s ),
  • р  + (обозначая набор n -кратных повторений строк из n набора r для любого ≥ 1), или
  • р  * (аналогично обозначает набор n -кратных повторений, но также включает пустую строку, рассматриваемую как 0-кратное повторение).

Например, используя Σ = {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. * .

Дюпон и др. показали, что множество всех структурно полных конечных автоматов [примечание 1] генерация заданного входного набора строк-примеров образует решетку с тривиальным недообобщенным и тривиальным сверхобобщенным автоматом в качестве нижнего и верхнего элемента соответственно.Каждый член этой решетки может быть получен факторизацией недообобщенного автомата соответствующим отношением эквивалентности .

Для приведенного выше примера набора строк {1, 10, 100} на рисунке внизу показан недообобщенный автомат A a,b,c,d в серый , состоящий из состояний а , б , с и д . На наборе состояний {a,b,c,d} существует всего 15 отношений эквивалентности, образующих решетку. Картирование [примечание 2] каждая эквивалентность E соответствующему факторавтоматному языку L ( A a,b,c,d / E ) получает частично упорядоченный набор, показанный на рисунке. Язык каждого узла обозначается регулярным выражением. Язык может распознаваться факторавтоматами по различным отношениям эквивалентности, все из которых показаны под узлом. Стрелка между двумя узлами указывает, что язык нижнего узла является подмножеством языка верхнего узла.

Если приведены как положительные, так и отрицательные примеры строк, Dupont et al. постройте решетку из положительных примеров, а затем исследуйте границу разделения между автоматами, генерирующими какой-либо отрицательный пример, и такими, которые этого не делают.Наиболее интересны те автоматы, которые находятся сразу под границей. [1] На рисунке границы разделения показаны для отрицательных строк примера 11 ( зеленый ), 1001 ( синий) , 101 ( голубой ) и 0 ( красный ).

Косте и Николас представляют собственный метод поиска внутри решетки, который они соотносят с парадигмой пространства версий Митчелла .Чтобы найти границу разделения, они используют алгоритм раскраски графа отношения неравенства состояния, вызванного отрицательными примерами. [2] Позже они исследуют несколько отношений упорядочения на множестве всех возможных слияний состояний. [3]

Кудо и Шимбо используют представление посредством автоматной факторизации, чтобы создать уникальную основу для следующих подходов (наброски показаны ниже ):

Показано, что каждый из этих подходов соответствует определенному виду отношений эквивалентности, используемых для факторизации. [5]

Подходы [ править ]

k -реверсивные языки [ править ]

Англуин рассматривает так называемые « k -обратимые» регулярные автоматы, то есть детерминированные автоматы, в которых каждое состояние может быть достигнуто не более чем из одного состояния, следуя цепочке переходов длины k .Формально, если Σ, Q и δ обозначают входной алфавит, множество состояний и функцию перехода автомата A соответственно, то A называется k -обратимым, если: ∀ a 0 , ..., a k ∈ Σ ∀ s 1 , s 2 ∈ Q : δ * ( s 1 , а 0 ... а k ) знак равно δ * ( s 2 , а 0 ... а k ) ⇒ s 1 знак равно s 2 , где δ * означает гомоморфное расширение δ на произвольные слова.Англуин предлагает кубический алгоритм изучения наименьшего k -обратимого языка по заданному набору входных слов; при k = 0 алгоритм имеет даже почти линейную сложность. [6] [7] Требуемая уникальность состояния после k + 1 заданных символов приводит к объединению состояний автомата, что приводит к правильному обобщению, отличному от тривиального недостаточно обобщенного автомата. Этот алгоритм использовался для изучения простых частей английского синтаксиса; [8] позже была предоставлена ​​дополнительная версия. [9] Другой подход, основанный на k -обратимых автоматах, — это метод хвостовой кластеризации . [10]

Автоматы-преемники [ править ]

Из заданного набора входных строк Вернада и Ришетен строят так называемый автомат-преемник , состоящий из одного состояния для каждого отдельного символа и перехода между состояниями каждых двух соседних символов. [11] Например, одноэлементный входной набор { aabbaabb } приводит к автомату, соответствующему регулярному выражению ( a + ⋅ b + ) * .

Расширением этого подхода является метод предшественника-преемника , который немедленно обобщает каждое повторение символа до числа Клини. + а затем включает для каждого символа набор его возможных предшественников в его состоянии.Автоматы-преемники смогут выучить именно тот класс локальных языков .Поскольку каждый регулярный язык является гомоморфным образом локального языка, грамматики первого класса можно выучить путем поднятия соответствующий (в зависимости от предполагаемого применения) гомоморфизм , если обеспечен .В частности, такой гомоморфизм существует для класса языков, изучаемых методом предшественника-преемника. [12] Изучаемость местных языков можно свести к изучению k -обратимых языков. [13] [14]

подходы Ранние ​ ​

Иллюстрация леммы о накачке для регулярных автоматов

Хомский и Миллер (1957) [15] использовали лемму о накачке : угадывают часть v входной строки uvw и пытаются встроить соответствующий цикл в обучаемый автомат; используя запросы на членство , они для соответствующего k спрашивают , какая из строк uw , uvvw , uvvvw , ..., uv к w также принадлежит изучаемому языку, тем самым уточняя структуру их автомата. В 1959 году Соломонов обобщил этот подход на контекстно-свободные языки , которые также подчиняются лемме о накачке . [16]

Прикрытие автоматов [ править ]

Кампеану и др. изучить конечный автомат как компактное представление большого конечного языка.Учитывая такой язык 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 . [17] На основе этого соотношения, отсутствие транзитивности которого [примечание 3] вызывает значительные технические проблемы, они дают O ( n 4 ) [примечание 4] Алгоритм построения из F автомата покрытия A с минимальным числом состояний.Более того, для объединения, пересечения и разности двух конечных языков они обеспечивают соответствующие операции на их автоматах покрытия. [18] [19] Паун и др. улучшить временную сложность до O ( n 2 ). [20]

Остаточные автоматы [ править ]

Производная Бжозовского (на красном фоне) набора словарных строк относительно " con "

Для набора S строк и строки u производная Бжозовского u −1 S определяется как набор всех остальных строк, которые можно получить из строки в S путем отрезания ее префикса u (если возможно), формально: u −1 S = { v ∈ Σ * : uv ∈ S } , ср. картина. [21] Денис и др. определим остаточный автомат как недетерминированный конечный автомат A , где каждое состояние q соответствует производной Бжозовского его принятого языка L ( A ), формально: ∀ q ∈ Q ∃ u ∈ Σ * : L ( А , q ) знак равно ты −1 L ( A ), где L ( A , q ) обозначает язык, принятый из q в качестве начального состояния.

Они показывают, что каждый регулярный язык порождается однозначно определенным минимальным автоматом-остатком. Его состояния являются ∪- неразложимыми производными Бжозовского, и он может быть экспоненциально меньшим, чем минимальный детерминированный автомат.Более того, они показывают, что остаточные автоматы для обычных языков не могут быть изучены за полиномиальное время, даже при условии оптимального набора входных данных.Они предлагают алгоритм обучения остаточных автоматов и доказывают, что он обучает автомат по характерной выборке положительных и отрицательных входных строк. [22] [23]

Обучение запросам [ править ]

Обычные языки невозможно выучить за полиномиальное время.используя только запросы членства [24] или используя только запросы эквивалентности. [25] Однако Англуин показал, что обычные языки можно выучить за полиномиальное время.используя запросы членства и запросы эквивалентности, а также предоставил алгоритм обученияназванный L*, который делает именно это. [26] Позднее алгоритм L* был обобщен для вывода NFA ( недетерминированных конечных автоматов ), а не DFA ( детерминированных конечных автоматов ), с помощью алгоритма, названного NL*. [27] Этот результат был далее обобщен, и был разработан алгоритм, который выводит AFA ( чередующиеся конечные автоматы ), названный AL*. [28] Отмечается, что NFA может быть экспоненциально более кратким, чем DFA, и что AFA может быть экспоненциально более кратким, чем NFA, и вдвойне экспоненциально более кратким, чем DFA. [29] Алгоритм L* и его обобщения имеют важное значение в области теории автоматов и формального изучения языков, поскольку они демонстрируют возможность эффективного изучения более выразительных моделей автоматов, таких как NFA и AFA, которые могут представлять языки более кратко и захватывать более сложные модели. шаблоны по сравнению с традиционными DFA.

Сокращенные регулярные выражения [ править ]

Брилл определяет сокращенное регулярное выражение как любое из

  • a (где a — любой символ из Σ; обозначает одноэлементный набор, содержащий только односимвольную строку a ),
  • ¬ a (обозначающий любой другой одиночный символ в Σ, кроме a ),
  • • (обозначает любой одиночный символ в Σ)
  • а * , (¬ a ) * , или • * (обозначая произвольное количество, возможно нулевое, повторений символов из набора a , ¬ a или • соответственно), или
  • r ⋅ s (где r и s , в свою очередь, являются более простыми сокращенными регулярными выражениями; обозначают набор всех возможных конкатенаций строк из набора r и s ).

Учитывая входной набор строк, он шаг за шагом строит дерево , каждая ветвь которого помечена сокращенным регулярным выражением, принимающим префикс некоторых входных строк, а каждый узел помечен набором длин принятых префиксов.Его цель - выучить правила исправления английских орфографических ошибок. [примечание 5] а не на теоретические размышления об обучаемости языковых занятий.Следовательно, он использует эвристику для сокращения древовидной структуры, что приводит к значительному улучшению времени выполнения. [30]

Приложения [ править ]

Примечания [ править ]

  1. ^ т.е. конечные автоматы без лишних состояний и переходов по заданному входному набору строк
  2. ^ Это отображение не является решеточным гомоморфизмом , а лишь монотонным отображением .
  3. ^ Например, F = { aab , baa , aabb } приводит к aab ~ aabb ( только z для проверки этого нужно учитывать = ε) и aabb ~ baa (аналогично), но не aab ~ baa (ввиду случая z = б ). По данным Кампеану и др. (2001, лемма 1, стр.5), однако x ~ y ∧ y ~ z → x ~ z справедливо для строк x , y , z с | х | ≤ | й | ≤ | г |.
  4. ^ где n — количество состояний DFA A F таких, что L ( A F ) = F
  5. ^ Например: Замените « прошлое » на « прошло » в контексте «(¬ t ⋅ o ) * ⋅ SINGULAR_NOUN ⋅ прошлое "

Ссылки [ править ]

  1. ^ П. Дюпон; Л. Микле; Э. Видаль (1994). «Что такое пространство поиска обычного вывода?». В РЦ Карраско; Дж. Ончина (ред.). Труды Второго международного коллоквиума по грамматическому выводу (ICGI): Грамматический вывод и приложения . ЛНКС. Том. 862. Спрингер. стр. 25–37. CiteSeerX   10.1.1.54.5734 .
  2. ^ Ф. Косте; Дж. Николас (1997). «Регулярный вывод как задача раскраски графа». Учеб. Семинар ICML по грамматическому выводу, автоматной индукции и овладению языком . стр. 9–7. CiteSeerX   10.1.1.34.4048 .
  3. ^ Ф. Косте; Дж. Николас (1998). «Как рассмотрение слияний несовместимых состояний может уменьшить дерево поиска по индукции DFA». В Васанте Хонаваре; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 199–210. CiteSeerX   10.1.1.34.2050 .
  4. ^ Доминик Люзо (август 1997 г.). «Универсальный подход к положительному выводу регулярной грамматики» . Учеб. 15-й Всемирный конгресс IMACS по научным вычислениям, моделированию и прикладной математике . Архивировано из оригинала 13 января 2005 г. Проверено 26 ноября 2013 г.
  5. ^ М. Кудо; М. Шимбо (1988). «Эффективные методы регулярного грамматического вывода с использованием частичных сходств и их логических отношений». Распознавание образов . 21 (4): 401–409. Бибкод : 1988PatRe..21..401K . дои : 10.1016/0031-3203(88)90053-2 .
  6. ^ Д. Англуин (1981). «Примечание о количестве запросов, необходимых для определения обычных языков». Информация и контроль . 51 : 76–87. дои : 10.1016/s0019-9958(81)90090-5 .
  7. ^ Д. Англуин (1982). «Вывод обратимых языков». Дж. АКМ . 293 (3): 741–765. CiteSeerX   10.1.1.232.8749 . дои : 10.1145/322326.322334 . S2CID   18300595 .
  8. ^ Роберт С. Бервик; Сэмюэл Ф. Пилато (1987). «Изучение синтаксиса методом автоматной индукции» . Машинное обучение . 2 (1): 9–38. дои : 10.1007/bf00058753 .
  9. ^ Раджеш Парех; Кодрин Никитиу; Васант Хонавар (январь 1997 г.). Полиномиальный алгоритм приращения времени для вывода регулярной грамматики (технический отчет). Исследовательская группа искусственного интеллекта, Университет штата Айова. п. 14. ТР 97-03.
  10. ^ Л. Микле; К. Фор (1985). Распознавание структурных образов: развитие и тенденции (Технический отчет). ИНРИА.
  11. ^ Ф. Вернада; М. Ришетен (1984). «Регулярный вывод для распознавания синтаксических образов: практический пример». Учеб. 7-я Международная конференция по распознаванию образов (ICPR) . стр. 1370–1372.
  12. ^ П. Гарсия; Э. Видаль; Ф. Касакуберта (1987). «Местные языки, метод преемника и шаг к общей методологии вывода регулярных грамматик». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 9 .
  13. ^ Такаси Ёкомори (октябрь 1989 г.). «Эффективное изучение контекстно-свободных языков». В КП Янтке [на немецком языке] (ред.). Учеб. Межд. Семинар АII . ЛНАИ. Том. 397. Спрингер. стр. 104–123. дои : 10.1007/3-540-51734-0_54 . ISBN  978-3-540-51734-4 .
  14. ^ Сатоши Кобаяши; Такаси Ёкомори (1994). «Изучение конкатенаций локально проверяемых языков на основе положительных данных». В Сэцуо Арикава; Клаус П. Янтке (ред.). Учеб. 5-й АЛТ . ЛНАИ. Том. 872. Спрингер. стр. 405–422. CiteSeerX   10.1.1.52.4678 .
  15. ^ Н. Хомский; Г. А. Миллер (1957). Концепция шаблона (Технический отчет). АСТИЯ. Документ AD110076.
  16. ^ Р. Соломонов (июнь 1959 г.). «Новый метод открытия грамматик языков фразовой структуры». Учеб. Межд. Конф. по обработке информации . Р.Ольденбург. стр. 285–290.
  17. ^ Это соотношение обобщает отношение R F из теоремы Майхилла-Нерода . Более подробно это было исследовано в разделе 3: Синтия Дворк; Ларри Стокмейер (1990). «Разрыв во временной сложности для двусторонних вероятностных конечных автоматов» . SIAM Journal по вычислительной технике . 19 (6): 1011–1023. дои : 10.1137/0219069 .
  18. ↑ Перейти обратно: Перейти обратно: а б Цезарь Кампеану; Николае Сантян; Шэн Юй (1998). «Минимальные автоматы-покрытия для конечных языков». В Ж.-М. Шампарно; Д. Морель; Д. Зиади (ред.). Учеб. Семинар по внедрению автоматов (WIA) (PDF) . ЛНКС . Том. 1660. Спрингер. стр. 43–56. CiteSeerX   10.1.1.37.431 . дои : 10.1007/3-540-48057-9_4 . ISBN  978-3-540-66652-3 .
  19. ^ Цезарь Кампеану; Николае Сантян; Шэн Юй (2001). «Минимальные автоматы-покрытия для конечных языков» . Теоретическая информатика . 267 (1–2): 3–16. CiteSeerX   10.1.1.550.3055 . дои : 10.1016/s0304-3975(00)00292-9 .
  20. ^ Андрей Паун; Николае Сантян; Шэн Юй (сентябрь 2001 г.). «О(н 2 ) Алгоритм построения автоматов с минимальным покрытием для конечных языков». В Шэн Ю; Андрей Паун (ред.). Материалы 5-й Международной конференции по реализации и применению автоматов (CIAA) (PDF) . LNCS. Том 2088. Springer . стр. 243–251 .  978-3-540-42491-8 .
  21. ^ Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID   14126942 .
  22. ^ Франсуа Дени; Орельен Лемей; Ален Терлютт (2000). «Изучение регулярных языков с использованием недетерминированных конечных автоматов». В Арлиндо Л. Оливейра (ред.). Грамматический вывод: алгоритмы и приложения, 5-й международный коллоквиум, ICGI . ЛНКС. Том. 1891. Спрингер. стр. 39–50. CiteSeerX   10.1.1.13.5559 . ISBN  978-3-540-41011-9 .
  23. ^ Франсуа Дени; Орельен Лемей; Ален Терлютт (2001). «Изучение обычных языков с использованием RFSA» (PDF) . Учеб. АЛЬТ '01 .
  24. ^ Англуин, Дана (1995). «Когда вопросы о членстве не помогут?». Материалы двадцать третьего ежегодного симпозиума ACM по теории вычислений - STOC '91 . стр. 444–454. дои : 10.1145/103418.103420 . ISBN  9780897913973 . S2CID   9960280 .
  25. ^ Англуин, Дана (1990). «Отрицательные результаты для запросов эквивалентности» . Машинное обучение . 5 (2): 121–150. дои : 10.1007/BF00116034 . S2CID   189902172 .
  26. ^ Англуин, Дана (1987). «Изучение регулярных наборов на основе запросов и контрпримеров» . Информация и вычисления . 75 (2): 87–106. дои : 10.1016/0890-5401(87)90052-6 .
  27. ^ Боллиг; Хабермель; Керн; Лейкер (2009). «Изучение NFA в англуинском стиле» (PDF) . 21-я Международная совместная конференция по искусственному интеллекту .
  28. ^ Англуин; Айзенштат; Фисман (2015). «Изучение обычных языков с помощью альтернативных автоматов» . 24-я Международная совместная конференция по искусственному интеллекту .
  29. ^ Майер, Арканзас; Стокмейер, Ларри Дж. (1995). «Сложность текстовых задач — на этот раз с чередованием» . Информация и вычисления . 115 .
  30. ↑ Перейти обратно: Перейти обратно: а б Эрик Брилл (2000). «Устранение неоднозначности на основе шаблонов для обработки естественного языка» (PDF) . Учеб. ЭМНЛП/ВЛК .
  31. ^ Алвис Бразма; Инге Йонассен; Яак Вило; Эско Укконен (1998). «Обнаружение закономерностей в биопоследовательностях». В Васанте Хонаваре; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 257–270.
  32. ^ М. С. Уотерман, изд. (январь 1989 г.). Математические методы исследования последовательностей ДНК . ЦРК Пресс. ISBN  978-0849366642 .
  33. ^ Фернандо Перейра; Ив Шабес (1992). «Внутри-внешняя переоценка для частично брекетированных корпораций» . Учеб. 30-я Энн. Заседание доц. для Комп. Лингвистика . стр. 128–135. дои : 10.3115/981967.981984 . S2CID   63967455 .
  34. ^ Хелена Ахонен (ноябрь 1996 г.). Создание грамматик для структурированных документов с использованием методов грамматического вывода (PDF) (доктор философии). Отчет. Том. А-1996-4. Хельсинкский университет, факультет компьютерных наук. S2CID   60722498 . Архивировано из оригинала (PDF) 12 февраля 2020 г.
  35. ^ Стивен Уоткинсон (1997). Индукция музыкального синтаксиса (Магистр). Кафедра искусственного интеллекта, унив. Эдинбург. Архивировано из оригинала 4 июня 2001 года.
  36. ^ Педро П. Крус-Алькасар; Энрике Видаль (1998). «Изучение регулярных грамматик для моделирования музыкального стиля: сравнение различных схем кодирования» (PDF) . В Васанте Хонаваре; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 211–222. дои : 10.1007/BFb0054077 . ISBN  978-3-540-64776-8 . S2CID   15302415 . Архивировано из оригинала (PDF) 16 февраля 2018 г.
  37. ^ Александр С. Саид; Суад Тайеб-бей (1998). «Грамматический вывод в распознавании документов». В Васанте Хонаваре; Гиора Слуцки (ред.). Грамматический вывод, 4-й международный коллоквиум, ICGI . ЛНКС. Том. 1433. Спрингер. стр. 100-1 175–186. ISBN  978-3-540-64776-8 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Induction_of_regular_languages&oldid=1228701338"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 014412f1d216a6a231904be05a880513__1718204460
URL1:https://arc.ask3.ru/arc/aa/01/13/014412f1d216a6a231904be05a880513.html
Заголовок, (Title) документа по адресу, URL1:
Induction of regular languages - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)