Нет, они не эквивалентны.Язык в 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 - равенство, подмножество,superset, none - вы обычно проверяете, является ли A подмножеством B, и является ли B подмножеством A. Вызовите первую проверку B1 и вторую проверку B2, где B1 и B2 являются булевыми переменными и являются истинными, если проверки пройдены (т.е., A является подмножеством B в случае B1, и B является подмножеством A в случае B2).Тогда (B1 && B2) соответствует равенству, (B1 &&! B2) соответствует подмножеству, (! B1 && B2) соответствует надмножеству, а (! B1 &&! B2) не соответствует никакой связи.
ВПример выше, я демонстрирую, что два языка не равны, демонстрируя, что RHS содержит элемент, не входящий в LHS.Обратите внимание, что это также исключает отношение «A является надмножеством B».Осталось два: B является надмножеством A, или между ними нет никакой связи.Чтобы решить это, вы должны определить, является ли A подмножеством B;все ли элементы на языке LHS на языке RHS.Если это так, LHS является подмножеством;в противном случае отношения отсутствуют.
Чтобы показать, что в одном наборе есть элемент, а не в другом, самый простой и убедительный подход - это контрпример на примере: назовите строку в одном, а не в другом.Это подход, который я принял.Вы также можете аргументировать, что язык должен содержать такой элемент, не называя его явно;этот вид доказательства может быть значительно труднее получить.
Чтобы показать, что каждый элемент множества A также находится в множестве B, вам понадобится более общий метод доказательства.Доказательство по индукции и доказательство от противного являются общими примерами.Чтобы сделать индуктивное доказательство, вы присваиваете - явно или неявно - натуральное число каждой строке в языке, демонстрируете, что ваше утверждение (в данном случае, что элемент также является элементом другого набора) верно с простым аргументом,Затем вы предполагаете, что это верно для первых n элементов в вашем наборе (в соответствии с нумерацией, которую вы даете), и показываете, что это подразумевает, что все последующие элементы также должны удовлетворять вашему требованию.Чтобы сделать доказательство от противного, вы предполагаете противоположное тому, что хотите доказать, и выводите противоречие.Если вы добились успеха, и ваше единственное предположение состояло в том, что ваше требование является ложным, значит, ваше требование должно быть верным все время.