3
$\begingroup$

So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting correct regexes at least to my knowledge, I was having some weird issues with variables/state names. Please help me understand what my mistake is here in my process:

Consider the DFA that is governed by these equations and $\Sigma = \{a, b\}$: $$Q_0 = bQ_2 \cup aQ_1 \\ Q_1 = bQ_2 \cup aQ_0 \\ Q_2 = aQ_2 \cup bQ_2 \cup \varepsilon$$

I'm sorry I don't have a picture of the graph, but I think this should be fairly simple to visualize. It is an unminimized DFA that pretty much accepts every string with at least 1 'b', as it bounces back and forth from $Q_1$ and $Q_0$ every time an 'a' is reached, both $Q_1$ and $Q_0$ have edges to $Q_2$ from 'b', and $Q_2$ is an accept state that stays at $Q_2$ no matter what character it sees. Now I attempt to do the reduction method we see in Raphael's post:

$Q_1 = bQ_2 \cup a(bQ_2 \cup aQ_1) \\ Q_1 = bQ_2 \cup abQ_2 \cup aaQ_1 \\ Q_1 = (b \cup ab)Q_2 \cup aaQ_1 \\ Q_1 = (aa)^*(b \cup ab)Q_2$

$\\ Q_2 = a^*bQ_2 \cup \varepsilon \\ Q_2 = a^*b^* \cup \varepsilon \\ Q_2 = (a^*b^*)^*$

$\\ \\ Q_1 = (aa)^*(b \cup ab)(a^*b^*)^*$

Now I have two questions here:

  1. Notice that at the end of my $Q_1$ manipulation I moved $(aa)^*$ to the front. This is something that I did out of common sense since thinking about the DFA, $(aa)^*$ has to be first since $Q_2$ doesn't have any outbound edges. Is there a way to formalize what I'm thinking/doing here?

  2. Notice that at the end I have my valid regex equal to $Q_1$. That doesn't seem right, since we want to find the regex associated with $Q_2$! But a quick simulation through my head tells me that it actually is the regex associated with $Q_2$. So what is going on?!

Thanks so much for your help.

$\endgroup$
1
  • $\begingroup$ In addition to D.W.'s comment below, I figured out that I was pretty much just skipping a step for my first question: it should be $Q_1 = (b \cup ab)Q_2 \cup aaQ_1 \Rightarrow Q_1 = aaQ_1 \cup (b \cup ab)Q_2 \Rightarrow Q_1 = (aa)^*(b \cup ab)Q_2$. This makes my application of Arden's Rule valid here. $\endgroup$ Dec 9, 2019 at 8:56

1 Answer 1

0
$\begingroup$

Your manipulation where you went from $Q_1 = (b \cup ab)Q_2 \cup aaQ_1$ to $Q_1 = (aa)^*(b \cup ab)Q_2$ was not valid. Instead, in this case I suggest that you first start by finding a nice form for $Q_2$, before trying to manipulate $Q_1$.

A good way to handle $Q_2$ is to note that $Q_2 = a Q_2 \cup b Q_2 \cup \epsilon$ implies $Q_2 = (a \cup b) Q_2 \cup \epsilon$ (by the distribute law); when then apply Arden's rule to conclude that $Q_2 = (a \cup b)^* \epsilon = (a \cup b)^*$.

Now plug in this expression for $Q_2$ into your equations for $Q_0$ and $Q_2$. You obtain

$$\begin{align*} Q_0 &= b (a \cup b)^* \cup a Q_1\\ Q_1 &= b (a \cup b)^* \cup a Q_0 \end{align*}$$

Next, take the expression for $Q_1$ and plug it into the first equation. We see that

$$Q_0 = b (a \cup b)^* \cup a b (a \cup b)^* \cup a a Q_0.$$

Now applying Arden's rule tells us that

$$Q_0 = (aa)^* (b \cup ab) (a \cup b)^*.$$

That's the regular expression that you ultimately wanted.

$\endgroup$
3
  • $\begingroup$ Great, thank you for clearing my confusion about applying Arden's rule. A quick question though, in your solution, we have $Q_0$ = (the regex we want). However, in my hypothetical DFA, $Q_2$ is the accept state, so shouldn't we be getting a regex for $Q_2$? Or are we trying to find a regex for the start state of the machine? Thanks so much. $\endgroup$ Dec 9, 2019 at 8:46
  • $\begingroup$ @CoolRobloxKid12, nope. The regexp that we get for $Q_0$ is the regexp that describes all strings that are accepted by the DFA, if you use $Q_0$ as the initial state of the DFA. That's what we want. The regexp we get for $Q_2$ describes all strings accepted by the DFA if you start at state $Q_2$ as your initial state. That's not what we want. $\endgroup$
    – D.W.
    Dec 9, 2019 at 8:55
  • $\begingroup$ Ok, thanks. I guess as a consequence to this then is that substituting for $Q_1$ producing the same regex is just a coincidence based on the way this DFA has been set up. Thank you so much for the help $\endgroup$ Dec 9, 2019 at 8:59

Your Answer

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

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