Определение, если два языка равны [Регулярное выражение]

Question

Готовилась к экзамену и переживала эту проблему:

Определить, является ли набор строк, представленных R1, подмножеством R2?

R1 = (01 +10)*      R2 = ((01)* + (10)*)

Моя попытка: так как там представлены одинаковые выражения, я попытался доказать, что они одинаковы R1 1 R2

Я попытался показать, что R2 такой же, как R1: поэтому я попробовал это, используя теорему эквивалентности регулярного выражения:

((01 + ε) * + (10 + ε)) = (01 + ε) + (10 + ε) *

теперь я застрял, я думаю о применении правила ассоциативности здесь и показать, что (01 + ε)* + (10 + ε)* = (01 + 10)* + (ε + ε)* = (01 + 10)* // Я думаю, что этот шаг может быть неправильным

таким образом R2 = R1

Шаг: (01 + ε)* + (10 + ε)* = (01 + 10)* + (ε + ε)* = (01 + 10)*

Я думаю, что это неправильно, я думаю, что я применяю закон ассоциативности неправильно, я не знаю, как его использовать, когда он имеет * на нем. Любая помощь на этом будет оценена. Пожалуйста:)

Answer 1

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

Начните с утверждения, что R1 является подмножеством R2 (строго или не должно иметь значения).

Обратите внимание, что R1 может произвести следующую строку (при условии + означает ИЛИ, поэтому R1 может производить либо 01 или же 10 по любому шаблону бесконечно)

10 01

Вы можете заметить, что невозможно создать эту строку в R2, поскольку R2 определен так, что он должен иметь только 01 пары или только 10 пар.

Следовательно, поскольку R1 может генерировать строки вне домена R2, R1 не может быть подмножеством, строгим или нет, R2.

Answer 2

Предположим, что R1 ⊆ R2. Поэтому каждая строка s в R1 также находится в R2.
Пусть s = "1001", который является членом R1; однако s не является членом R2. =><=

Поскольку R1 не является подмножеством R2, все, что вам нужно показать, это контрпример.