I'm currently working on solving a question that requires determining which of the given regular expressions is equivalent to the language of the DFA provided. However, I'm encountering two primary challenges. First, I'm struggling to derive a regular expression from the DFA on my own. Second, I'm unsure about how to demonstrate the equivalence of these three regular expressions.
Is there a systematic approach for simplifying regular expressions and deriving regular expressions from a given DFA, or vice versa, transforming regular expressions into DFAs? My initial attempt involved tracing all the paths from the initial state to the final state, but unfortunately, that method didn't yield the desired results.
- $(aa)^*(ab+\lambda)(bb)^*$
- $(aa)^*((bb)^*+a(bb)^*b)$
- $(aa)^*(bb)^*+a(aa)^*b(bb)^*$
For your bottom three equivalence, depends how much rigor your professor wants but we can see from
1.) $(aa)^*(ab+\lambda)(bb)^*$
2.) $(aa)^*((bb)^*+a(bb)^*b)$
3.) $(aa)^*(bb)^*+a(aa)^*b(bb)^*$
I will explain how these are all equivalent and simplify to the third one: $(aa)^*(bb)^* + a(aa)^*b(bb)^*$ (i.e. how you get all the words that either have a strictly even # of $a$'s and $b$'s or have a strictly odd # of $a$'s and $b$'s
You can think about "multiplying" these out (very carefully) as terms are typically not commutative.
1.) So for the first one we have: $$(aa)^*(ab+\lambda)(bb)^*=(aa)^*ab(bb)^*+(aa)^*\lambda(bb)^*=(aa)^*ab(bb)^*+(aa)^*(bb)^*$$ we can then actually move the singular $a$ in front of the $(aa)^*$ because the $a$ letters themselves are nondistiguishable (Note you wouldn't be able to do this and show that $(ab)^*a=a(ab)^*$), so we get: $$(aa)^*(ab+\lambda)(bb)^*=a(aa)^*b(bb)^*+(aa)^*(bb)^*=(aa)^*(bb)^*+a(aa)^*b(bb)^*$$ as desired.
2.) For the second one we have: $$(aa)^*((bb)^*+a(bb)^*b)=(aa)^*(bb)^*+(aa)^*a(bb)^*b=(aa)^*(bb)^*+a(aa)^*b(bb)^*$$ as desired (you can see I moved the singular $a$ in front of the $(aa)^*$ and separately the singular $b$ in front of the $(bb)^*$ as I explained with the $a$'s earlier).
So we have showed that 1.), 2.), and 3.) are equivalent.
Just to reiterate, the reason we can pull the singular values, WLOG $a$ in front of their corresponding $(aa)^*$ is because $$(aa)^*a=a(aa)^*$$ as it doesn't matter if we choose our even # of $a$'s first then tack on an extra at the end versus having one $a$ then adding all your additional even # of $a$'s after.
Hope that makes sense. Still new to explaining things, especially through text, so if you need clarification on this, do comment.
The DFA shown seems to accept any words $w\in(aa)^*(bb)^*+a(aa)^*b(bb)^*$.