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

Question

подготовка к экзамену и проходил через эту проблему:

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

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

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

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

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

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

, таким образом, R 2 = R 1

стадия: (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, поэтому все, что вам нужно показать, является контрпримером.