Блог

Является ли следующая эквивалентность регулярных выражений истинной? Почему или почему нет?

(ab)* u (aba)* = (ab u aba)*

* = Звезда Клини

u = Объединение (теория множеств)

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

Редактировать:

Просто чтобы немного разъяснить для заинтересованного читателя. Языки представляют собой наборы строк. Следовательно, отношения между наборами также являются отношениями между языками. Наиболее распространенными отношениями между множествами являются равенство, подмножество и надмножество. Учитывая два множества 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, и в то же время B содержит элемент, которого нет в A.

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

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

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

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

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

Сходства:

1. оба принимают пустую строку
2. оба принимают «abeba» (минимальное выражение регулярного выражения2)

Различия:

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

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

НО

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