1
$\begingroup$

Check if these 2 regular expressions are equivalent:

$R_1 = (a+b)^*(aa+bb)$

$R_2 = (a+b)^*aa+a^*bb+b^+b$

My approach:

We check if both of these expressions generate the same set of strings. Meaning that any string that can be generated by $R_1$ can also be generated by $R_2$, and vice versa.

$R_1$ can generate strings starting with empty string, or one or more occurrences of $a$ or $b$ and ending with either $aa$ or $bb$.

The start of the word $(a+b)^*$ generated by $R_1$ can also be generated by $R_2$ with $(a+b)^*$, so we can break down the cases based on the ending of the $R_1$ strings:

  1. $R_1$ ends with $aa$ – can be generated by $R_2 = (a+b)^*aa$
  2. $R_1$ ends with $bb$ – can be generated by $R_2 = (a+b)b^+b$ (where $b^+=b$)

Thus $R_1 ⊆ R_2$.

No we check it for the other way. Again the start of the word $(a+b)^*$ generated by $R_2$ can also be generated by $R_1$ with $(a+b)^*$, so we can break down the cases based on the ending of the $R_2$ strings:

  1. $R_2$ ends with $aa$ – can be generated by $R_1 = (a+b)^*(aa)$
  2. $R_2$ ends with $a^*bb$ – can be generated by $R_1 = (a+b)^*(bb)$, because $(a+b)^*a^* = (a+b)^*$
  3. $R_2$ ends with $b^+b$ – can be generated by $R_1 = (a+b)^*(bb)$, because $b^+b = b^*bb$ and again $(a+b)^*b^* = (a+b)^*$

Thus $R_2 ⊆ R_1$.

We get that $R_1$ and $R_2$ are equivalent.

Is this approach correct for this case? I know that for more complex expressions it would be easier to compares the corresponding DFA's.

$\endgroup$
2
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Apr 17, 2023 at 18:19
  • $\begingroup$ I believe there is a misprint in the task (you forgot parentheses in the second part of $R_2$), since the given expressions are not equivalent ($R_1$ recognizes $babb$, while $R_2$ does not) $\endgroup$
    – Tonita
    Apr 19, 2023 at 7:37

1 Answer 1

1
$\begingroup$

Yes, the approach is correct, but there are some mistakes:

  1. Statements such as

    • $R_1$ ends with $aa$ – can be generated by $R_2 = (a+b)^*aa$

    are a bit sloppy. What you mean to say is:

    • $R_2$ is the union of 3 expressions, $R_{2,1}, R_{2,2}, R_{2,3}$
    • $R_1$ can be written as the union of 2 expressions, $R_{1,1}$ and $R_{1,2}$
    • hence, to prove equality, it suffices to show that $\forall x \exists y: L(R_{1,x}) \subseteq L(R_{2,y})$, and vice versa (5 statements in all)
    • and then you proceed to prove those 5 statements
  2. One of those 5 statements is incorrect, and there is a mistake in the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.