Объекты, операции, регулярные выражения и конечные автоматы

Вступление

Эта статья предназначена для мягкого введения в теорию формального языка. Как и во всем остальном, мы постараемся сбалансировать математическую строгость с конкретными примерами, имеющими лингвистически мотивированные примеры.

Темы для обсуждения:

  • Элементарная формальная теория языка
  • Обычные языки
  • Регулярные выражения
  • Языки
  • Конечные автоматы
  • Регулярные отношения

Основные понятия

Наборы и элементы

Формальные языки имеют определенный, определенный алфавит. алфавит может быть обозначен ∑.

Этот алфавитный набор состоит из элементов, называемых буквами. Этот набор - конечный набор. Каждая буква представляет собой символ, который может быть от «abc…», «123…». Символы могут быть даже словами.

Последовательность букв может называться словом или строкой.

Тогда это примеры строки:

  • Кот
  • Арахнадискотека
  • ASKdnskjf
  • ууууууу
  • Оууууу
  • ksdjfnskdjfnSOULJABOITELLEMksjdnfksjdnf

Длина строки

Длина строки или количество символов в строке обозначается | w |.

Пустой строки

Считаем пустую строку нулевой длины единственной и обозначаем через ϵ.

Конкатенационная операция

Конкатенация - это сложение двух строк вместе, где имеет значение порядок. Например, «искусственный» + «интеллект» = «искусственный интеллект». Данный:

Конкатенация обозначается:

Обратите внимание, что:

Для каждой строки w:

Некоторые примеры:

  • «Учиться» + «с»
  • «Узнать» + «изд»
  • «Учиться» + «инг»

Экспонентная операция

Для каждой строки w:

  • w⁰=ϵ

Для всех показателей n ›0:

  • wⁿ=wⁿ⁻¹ ⋅ w

Например:

Если w = "go", то:

  • w⁰=ϵ=””
  • w¹=w=”go”
  • w² = w * w = "гого"
  • w³ = w * w * w = «гого»

Реверсивная операция

Если w - строка, то обратное w будет:

Палиндром определяется:

Здесь мы имеем в виду такие слова, как «ана», «анна», «гоночный автомобиль» и т. Д. Я не уверен, что это технически называется симметрией. Но все бы поняли, что я имею в виду, если бы я назвал эти слова симметричными. Если в теории формального языка существует такое понятие, как симметрия, мне интересно, как оно связано с теорией групп.

По совпадению теория групп возникла из-за нашей потребности изучать симметрию геометрических объектов и пространств. Где мы могли бы построить теорию точно так же, как построена теория формального языка, используя множества в качестве объектов, а затем определяя стандартные операции.

Об этом позже…

Набор подстрок или подмножество строк

Если w - строка, то подстрока w - это последовательность, образованная путем взятия смежных символов w в том порядке, в котором они встречаются в w.

является подстрокой w тогда и только тогда, когда есть 2 другие подстроки такие, что

Также w₁ и wᵣ могут быть пустыми строками. Эти две подстроки являются частными случаями именованных подстрок, префикса и суффикса.

Формальный язык

Для алфавита множество всех строк в алфавите обозначается как ∑ *.

Обратите внимание: пока в нашем алфавите есть хотя бы 1 символ, набор всей строки в нашем алфавите бесконечен. Итак, учитывая, что формальным языком является любое подмножество ∑ *, существует бесконечное количество формальных языков в одном и том же алфавите.

Формальный язык - это буквально набор строк. Тем не менее, все естественные языки технически представляют собой просто набор слов.

Английский язык - это просто набор всех английских слов. Связи с идеями и действиями не являются частью языка по этому определению.

Это латинский алфавит, и вот несколько примеров формальных языков:

  • ∑*
  • Набор строк, состоящих только из согласных звуков
  • Набор строк, состоящий только из одной гласной и одной согласной
  • Набор всех однобуквенных слов
  • Набор всех слов, встречающихся в определенной книге

Поскольку некоторые из этих множеств бесконечны, а другие конечны, языки, которые их представляют, также бесконечны и конечны.

Расширение строковых операций на языки

Точно так же, как строки могут иметь операции. Некоторые из этих операций также работают с языками, которые представляют собой наборы строк. Например, если L - язык, то Lᵣ - это язык, в котором все строки противоположны строке в L.

Еще одна операция, которая работает с языками, - это конкатенация. Для языков L и M конкатенированный язык LM - это язык, в котором все его строки являются конкатенированными строками L и M.

Клини Закрытие

Пусть L = {собака, кошка}.

Обратите внимание:

  • L⁰ ={},
  • L¹ = {собака, кошка},
  • L² = {кошка, кошка, собака, собака}
  • и т.п.

Таким образом, L * содержит среди своего бесконечного набора строк строки: {ϵ, cat, dog, catcat, catdog, dogcat, dogdog, catcatcat, catdogcat, dogcatcat, dogdogcat и т. Д.}

Замыкание Клини как набор всех струн над алфавитом

Рассмотрим алфавит ∑ = {a, b} и язык L = {a, b}, определенный над ∑. L * - это набор всех строк над a и b, что также является точным определением ∑ *.

∑ * - это частный случай L *, где L = ∑.

Языковые классы и лингвистические формализмы

Формальные языки - это наборы строк. И их можно построить любым доступным для множеств методом. В общем, это не очень полезно. Итак, для довольно простых языков мы вводим идею правил. Правила характеризуют язык, так что мы можем отделить языки друг от друга, используя эти правила. Мы обозначаем языки с помощью:

Кроме того, мы обозначаем классы языков с помощью:

Для конкретного языка интересующим свойством этого языка является замыкание. Например, для бинарной операции, такой как объединение, мы хотим знать, закрыт ли язык при операции объединения.

Есть способ проверить, закрыт ли класс языков при выполнении какой-либо операции. В основном, если два языка находятся в классе независимо друг от друга. И язык, полученный в результате работы двух языков, также находится в классе.

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

Алгоритмы, определяющие принадлежность, называются алгоритмами распознавания. Как правило, чем выразительнее класс, тем сложнее определить его принадлежность к языкам.

Если дополнительно алгоритм навязывает структуру строке, это называется алгоритмом синтаксического анализа.

Регулярные выражения

Регулярное выражение - это разновидность лингвистического формализма. В частности, это выражения на некотором алфавите ∑, дополненные некоторыми специальными символами.

Обозначение - это отображение регулярных выражений в наборы строк над ∑, так что каждое правильно сформированное регулярное выражение обозначает набор строк или язык.

Помните, что язык - это просто набор строк.

ОПРЕДЕЛЕНИЕ 1. Для алфавита ∑ набор регулярных выражений над определяется следующим образом:

  • ∅ - регулярное выражение, {}
  • ϵ - регулярное выражение, {""}
  • если a ∈ ∑ - буква, то a - регулярное выражение
  • если r₁ и r₂ - регулярные выражения, то (r₁ + r₂) и (r₁⋅ r₂) тоже.
  • если r - регулярное выражение, то и (r) * тоже.
  • ничего больше не является регулярным выражением над ∑

Пусть Σ - алфавит {a, b, c,. . . , y, z}. Некоторые регулярные выражения в этом алфавите:

  • ∅,
  • a,
  • ((c · a) · t),
  • (((m · e) · (o)∗) · w),
  • (a + (e + (i + (o + u)))),
  • ((a + (e + (i + (o + u)))))∗,
  • и т.п.

ОПРЕДЕЛЕНИЕ 2. Для регулярного выражения r его обозначение, || r ||, представляет собой набор строк, определенных следующим образом:

  • ∅ - регулярное выражение, {} пустое множество
  • ϵ - регулярное выражение, {""}, одноэлементный набор с пустой строкой
  • если a ∈ ∑ - буква, то a - регулярное выражение, {a}, одноэлементный набор со строкой
  • если r₁ и r₂ - два регулярных выражения с обозначениями [[r₁]] и [[r₂]], соответственно, то [[(r₁ + r₂)]] = [[r₁]] ∪ [[r₂]] и [[ (r₁ · r₂)]] = [[r₁]] · [[r₂]];
  • если r - регулярное выражение с обозначением [[r]], то [[(r) ∗]] = [[r]] ∗.

Здесь обычно скобки можно опустить, чтобы ((a + (e + (i + (o + u))))) ∗ превратилось в (a + e + i + o + u) ∗.

Регулярные выражения становятся очень полезными при определении бесконечных языков или наборов строк. Потому что конечные языки можно перечислить и просто записать.

Учитывая алфавит, состоящий из всех английских букв, Σ = {a, b, c,. . . , y, z} язык Σ ∗ обозначается регулярным выражением Σ ∗.

Множество всех строк, содержащих гласную, обозначается Σ ∗ · (a + e + i + o + u) · Σ ∗.

Множество всех строк, начинающихся с «un», обозначается (un) Σ ∗. Множество строк, заканчивающихся либо на «тион», либо на «сион», обозначается Σ ∗ · (s + t) · (ion).

Обратите внимание, что все эти языки бесконечны.

ОПРЕДЕЛЕНИЕ 3. Язык L является регулярным, если существует регулярное выражение r такое, что L = || r ||.

Класс языков L, который может быть выражен как обозначение регулярных выражений, называется регулярными языками. Что также способствует существованию нерегулярных языков.

Свойства регулярных языков

Мотивация к изучению обычных языков проистекает из того факта, что они обладают некоторыми довольно интересными свойствами. Например, поскольку эти языки легко резюмируются с помощью набора обозначений. Легко создать некоторые леммы, такие как их замкнутость относительно объединения, конкатенации и замыкания Клини.

Для двух регулярных языков, L1 и L2, должно существовать два регулярных выражения, r1 и r2, такие, что [[r1]] = L1 и [[r2]] = L2. Таким образом, можно формировать новые регулярные выражения на основе r1 и r2, например r1 · r2, r1 + r2 и r ∗ 1.

Из определения регулярных выражений и их обозначений следует, что обозначение r1 · r2 - L1 · L2: [[r1 · r2]] = L1 · L2. Поскольку r1 · r2 - регулярное выражение, его обозначение - регулярный язык, и, следовательно, L1 · L2 - регулярный язык.

Шули Винтнер. Теория формального языка для обработки естественного языка. Эффективные инструменты и методики обучения обработке естественного языка и компьютерной лингвистике, семинар ACL’02, Филадельфия, штат Пенсильвания, июль 2002 г.

Обычные языки, как известно, закрываются при многих операциях:

  • Пересечение
  • Дополнение
  • Возведение в степень
  • Замена
  • Гомоморфизм

Также обратите внимание, что нестандартные сложные языки не демонстрируют такого приятного поведения.

Конечные автоматы

Мы используем регулярные выражения, чтобы указать набор, обобщающий регулярный язык. Мы добавим еще один формализм в наше изучение языков. Здесь мы определим языки как сущности, порожденные вычислением.

Также как двойственная природа материи как частицы и волны. Язык имеет двойную природу: он представляет собой набор строк и результат вычислительного процесса.

Этот вычислительный процесс называется конечным автоматом. Существует обобщенная версия конечного автомата, но здесь мы определяем наши автоматы для языковой обработки.

ОПРЕДЕЛЕНИЕ 4. Конечная автоматизация - это набор из пяти элементов (Q, q₀, ∑, δ, F), где:

  • ∑ - конечное состояние символов алфавита
  • Q - конечный набор состояний
  • q₀ ∈ Q - начальное состояние
  • F ⊆ Q - множество конечных состояний, подмножество Q
  • δ: Q × ∑ × Q - отношение состояний и символов алфавита к состояниям

ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ. Конечные автоматы изображаются графически в виде графиков. Где у нас есть узлы и ссылки. Представьте себе каждый узел как состояние и каждую ссылку, представляющую букву алфавита.

Конечный автомат A, определяемый формулой (Q, q₀, ∑, δ, F), где:

  • ∑ = {c,a,t,r}
  • Q={q₀,q₁,q₂,q₃}
  • F={q₃}
  • δ={(q₀,c,q₁), (q₁,a,q₂), (q₂,t,q₃),(q₂,r,q₃)}

ОПРЕДЕЛЕНИЕ 5. Учитывая конечную автоматизацию A, определенную как (Q, q₀, ∑, δ, F), рефлексивное транзитивное замыкание переходного отношения δ: Q × ∑ × Q равно δ ^, определяется:

  • для любого состояния q ∈ Q, (q, ϵ, q) ∈ δ ^
  • для каждой строки w ∈ ∑ * и буквы a ∈ ∑
  • если (q, w, q ’) ∈ δ ^ и (q’, a, q ’’) ∈ δ, то (q, w ⋅ a, q ’’) ∈ δ ^

Строка w принимается A тогда и только тогда, когда существует состояние q ∈ F такое, что δ ^ (q₀, w) = q. Язык A - это набор всех строк, принимаемых A: L (A) = {w | существует q ∈ F такое, что δ ^ (q₀, w) = q}.

Помните, что конечный автомат определен только для отношений перехода от узла к узлу. Чтобы иметь возможность определять язык с помощью FSA, нам нужно расширить это отношение перехода с узла на пути. Если отношение перехода обозначается δ, то рефлексивное транзитивное замыкание обозначается δ ^. Рефлексивный означает, что каждый элемент в узлах может иметь отношение к себе, в то время как транзитивность подразумевает, что вместо другого узла он охватывает цепочку узлов.

Это отношение присваивает каждому пути непустую строку. В то время как пустая строка приравнивается к пустому пути, что означает, что это отношение к себе. Поскольку это расширение FSA, нас по-прежнему интересуют пути, которые начинаются в q₀ и заканчиваются в q.

Пока строка имеет связанный путь, определенный FSA, мы говорим, что строка является частью языка. Это означает, что пути, заканчивающиеся на неофициальный q, не являются частью языка.

Следующие примеры продемонстрируют разницу между определениями 4 и 5. Возьмем следующий конечный автомат. По определению 4 у нас есть такие строки, как c, a, t, r.

В то время как с расширенным определением 5 у нас есть строки cat и car. Поскольку наше δ ^ позволяет:

Отношения с самими собой

  • (q₀,ϵ, q₀), (q₁,ϵ, q₁), (q₂,ϵ, q₂), (q₃,ϵ, q₃)

Пути

  • (q₀,c, q₁), (q₁, a, q₂), (q₂,t, q₃), (q₂,r, q₃)
  • (q₀,ca, q₂), (q₁,at, q₃), (q₁,ar, q₃)
  • (q₀, кот, q₃), (q₀, машина, q₃)

Обратите внимание, что не все пути идут от начального состояния к конечному состоянию. Следовательно, в этом FSA используется следующий язык: {кошка, машина}.

Теперь мы немного расширим наше определение, включив ϵ - ходы. Это в основном позволяет FSA перемещаться по определенным штатам.

Везде, где есть ϵ, FSA может переходить из одного состояния в другое, не печатая буквы или символа. Для этой диаграммы язык имел бы {do, undo, undone, done}.

Конечные автоматы - это один из двух способов определения языков, другой способ - регулярные выражения. Оказывается, класс языков, который может быть сгенерирован с помощью FSA, - это обычные языки.

ТЕОРЕМА 1. Язык L является регулярным тогда и только тогда, когда существует такое FSA A, что L = L (A).

Другие статьи

This post is part of a series of stories that explores the fundamentals of natural language processing:
1. Context of Natural Language Processing
Motivations, Disciplines, Approaches, Outlook
2. Notes on Formal Language Theory
Objects, Operations, Regular Expressions and Finite State Automata

Следующий…

В следующей статье мы рассмотрим иерархию языков Хомского, поскольку она является одним из формальных столпов компьютерной лингвистики, и ее результаты продолжают определять современные исследования и разработки в области НЛП.

Чтобы просмотреть содержание и другие материалы, нажмите здесь.

использованная литература

Кларк, Александр. Справочник по компьютерной лингвистике и обработке естественного языка. Вили-Блэквелл, 2013.

Эйзенштейн, Якоб. Введение в обработку естественного языка. MIT Press, 2019.

Берд, Стивен и др. Обработка естественного языка с помощью Python. О’Рейли, 2009.

Джурафски, Дэн и Джеймс Х. Мартин. Обработка речи и языка. Пирсон, 2014.

Баркер-Пламмер, Дэйв и др. Язык, доказательства и логика. CSLI Publ., Центр изучения языка и информации, 2011 г.