Эквивалентности регулярных выражений

Нет, они не эквивалентны. Язык справа содержит «абааб», а язык слева — нет. Есть ли между ними какая-либо связь? Да; но я не просто дам вам ответ. Подсказка: есть ли строки в правой части, которых нет в левой?

РЕДАКТИРОВАТЬ:

Просто поясню немного для заинтересованного читателя. Языки — это наборы строк. Следовательно, отношения между множествами являются также отношениями между языками. Наиболее распространенными отношениями множества являются равенство, подмножество и надмножество. Для заданных двух множеств A и B над множествами универсума U1 и U2 множество A является подмножеством B относительно множества универсума U1 u U2 (u обозначает объединение), если и только если каждый элемент A также является элементом B. Аналогично, для двух множеств A и B над множествами универсума U1 и U2, множество A является надмножеством B относительно множества универсума U1 u U2 (u означает объединение) тогда и только тогда, когда каждый элемент B также является элементом A (эквивалентно, если и только если B является подмножеством A) . Множества A и B равны тогда и только тогда, когда A является подмножеством B, а B является подмножеством A (эквивалентно, если A является надмножеством B и B является надмножеством A). Обратите внимание, что два набора A и B не обязательно должны быть в любом из этих трех отношений; это происходит, когда А содержит элемент, которого нет в В, и в то же время В содержит элемент, которого нет в А.

Чтобы выяснить, какое из четырех возможных отношений существует между множествами A и B — равенство, подмножество, надмножество, отсутствие — вы обычно проверяете, является ли A подмножеством B и является ли B подмножеством A. Вызовите первую проверку B1, а вторую check B2, где B1 и B2 — булевы переменные и истинны, если проверки пройдены успешно (т. е. A — подмножество B в случае B1, а B — подмножество A в случае B2). Тогда (B1 && B2) соответствует равенству, (B1 && !B2) соответствует подмножеству, (!B1 && B2) соответствует надмножеству и (!B1 && !B2) соответствует отсутствию связи.

В приведенном выше примере я демонстрирую, что два языка не равны, демонстрируя, что правая часть содержит элемент, которого нет в левой части. Обратите внимание, что это также исключает отношение «A является надмножеством B». Остаются два: B является надмножеством A, или между ними нет никакой связи. Чтобы решить это, вы должны определить, является ли A подмножеством B; все ли элементы языка LHS находятся на языке RHS. Если это так, LHS является подмножеством; иначе отношений нет.

Чтобы показать, что в одном множестве есть элемент, а в другом нет, самым простым и наиболее убедительным подходом является доказательство контрпримером: назвать строку в одном, но не в другом. Это подход, который я принял. Вы также можете аргументировать, что язык должен содержать такой элемент, не называя его явным образом; такое доказательство может быть значительно сложнее получить правильно.

Чтобы показать, что каждый элемент множества A находится также и в множестве B, вам понадобится более общий метод доказательства. Доказательство по индукции и доказательство от противного являются общими примерами. Чтобы провести индуктивное доказательство, вы назначаете — явно или неявно — натуральное число каждой строке языка, демонстрируете, что ваше утверждение (в данном случае, что элемент также является элементом другого множества) верно с помощью простого аргумента. . Затем вы предполагаете, что это верно для первых n элементов в вашем наборе (в соответствии с указанной вами нумерацией), и показываете, что это означает, что все элементы, которые следуют после, также должны удовлетворять вашему требованию. Чтобы провести доказательство от противного, вы предполагаете противоположное тому, что хотите доказать, и получаете противоречие. Если вы преуспели, и ваше единственное предположение состояло в том, что ваше утверждение ложно, то ваше утверждение должно было быть верным с самого начала.

Нет, они не эквивалентны.

Сходства:

1. оба принимают пустую строку
2. оба принимают "ababa" (минимальное выражение regex2)

Различия:

1. ab и aba могут появляться один раз или нет в regex1, в отличие от regex2, они могут появляться или нет, но в соединении.

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

НО

Поскольку регулярное выражение является представлением (а не описанием) регулярного языка, вы не можете сказать, что regex1 эквивалентно regex2. просто взглянув на выражение, чтобы доказать его (математическое доказательство), вы можете преобразовать эти регулярные выражения в NFA (недетерминированные конечные автоматы) или DFA (детерминированные конечные автоматы) и сравнить различия .