1
$\begingroup$

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.

enter image description here

  1. $(aa)^*(ab+\lambda)(bb)^*$
  2. $(aa)^*((bb)^*+a(bb)^*b)$
  3. $(aa)^*(bb)^*+a(aa)^*b(bb)^*$
$\endgroup$

1 Answer 1

3
$\begingroup$

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)^*$.

$\endgroup$
7
  • 1
    $\begingroup$ @MishaLavrov Good catch, thank you. I did edit after your comment to say consecutive but that is not true either. At some point I will formulate all the words $w\in(aa)^*(bb)^*+a(aa)^*b(bb)^*$ into spoken english. For now, I'm hoping the simplification done earlier will be good enough for OP to understand the DFA diagram. $\endgroup$
    – DoubleV
    Oct 11, 2023 at 16:04
  • 2
    $\begingroup$ I would phrase it as "any word of even length consisting of a possibly-empty sequence of $a$'s followed by a possibly-empty sequence of $b$'s". $\endgroup$ Oct 11, 2023 at 16:26
  • 1
    $\begingroup$ @MishaLavrov very elegant and concise. Something I need to work on! $\endgroup$
    – DoubleV
    Oct 11, 2023 at 16:53
  • 2
    $\begingroup$ @Ariana some DFA's can be much more complicated than others so looking at a bunch of examples and trying to understand each is the best. For this one, notice how we have two accept states (state 0 or 2), one that you start at but can loop to an infinite amount of times (each time we input an even # of $a$'s). We then, if we are to input a $b$ (which is optional, we could just stop at an even # of $a$'s), we then have two options: #1 input the $b$ when we are on the accept state (0) with an even # of $a$'s or #2 input the $b$ when we are on the non-accept state (1) with an odd # of $a$'s $\endgroup$
    – DoubleV
    Oct 12, 2023 at 10:53
  • 1
    $\begingroup$ @Ariana for option #1, if we input $b$ from the accept state (0) we get sent to state 3. From there, we must input a second $b$ to get to state 2 if we have any shot of this being a valid word. So we now have 2 $b$'s. From here on the accept state, we can see that similarly we can loop an infinite amount of times (each time we input an even # of $a$'s). Exploring option #2 above should be very similar logic. You have an odd # of $a$'s, input a $b$ sending you to accept state 2 so adding any additional even # of $b$'s will bring you back to the accept state so you will have an odd # of $b$'s. $\endgroup$
    – DoubleV
    Oct 12, 2023 at 10:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .