Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

enter image description here

This is a NFA, I have been working to covert it to a regular expression. After I'am done, I arrive at an expression as follows

$$ \left(((a\cup b)a^*b) (ba^*b)^*a\right)^* \left(((a\cup b)a^*b) (ba^*b)^*\right) $$

Now, I really doubt if the answere is correct if anyone could help. I used the state removal method.

share|cite|improve this question
If I counted parentheses correctly, the regular expression doesn't seem to accept an empty string. – JiminP Aug 23 '13 at 16:52
up vote 10 down vote accepted

I am going to write $S_i$ for the set of strings that cause the machine to go from the start state into state $i$.

From the diagram of the machine, we have:

$$\begin{align} \def\a{\mathtt{a}}\def\b{\mathtt{b}} S_1 & = \epsilon + S_3\a \\ S_2 & = S_1(\a+\b) + S_2\a + S_3\b \\ S_3 & = S_2\b \end{align}$$

(This part is crucial, and if you don't find this obvious, and don't see where I got these equations, leave a comment so I can explain it.)

After this it is all mechanical. Substituting $S_3$ into the equations for $S_1$ and $S_2$ gives:

$$\begin{align} S_1 & = \epsilon + \color{blue}{S_2\b}\a \\ S_2 & = S_1(\a+\b) + S_2\a + \color{blue}{S_2\b}\b \\ & = \color{darkred}{S_1(\a+\b) + S_2(\a + \b\b)} \\ S_3 & = S_2\b \end{align}$$

We can eliminate $S_2$ from its definition using the rule that says that if $X = p + Xq$ then $X = pq^*$:

$$\begin{align} S_1 & = \epsilon + S_2\b\a \\ S_2 & = S_1(\a+\b) + S_2(\a + \b\b) \\ & = \color{darkred}{S_1(\a+\b)(\a + \b\b)^*} \\ S_3 & = S_2\b \end{align}$$

Then we put the definition of $S_2$ into $S_1$ and apply the $X = p + Xq\implies X = pq^*$ transformation to it:

$$\begin{align} S_1 & = \epsilon + \color{blue}{S_1(\a+\b)(\a + \b\b)^*}\b\a \\ & = \color{darkred}{\left((\a+\b)(\a + \b\b)^*\b\a\right)^*}\\ S_2 & = S_1(\a+\b)(\a + \b\b)^* \\ S_3 & = S_2\b \end{align}$$

Now we have an explicit formula for $S_1$ (which it's not hard to see is correct), we could substitute this into the equations for $S_2$ and $S_3$ to get explicit formulas for the strings accepted in those states, but what we really want is to know the strings accepted by the entire automaton, which is exactly $$\begin{align}S_1 + S_3 & = S_1 + S_2\b \\ & = S_1 + S_1(\a+\b)(\a + \b\b)^*\b \\ & = S_1(\epsilon + (\a+\b)(\a + \b\b)^*\b)\end{align}$$

and since $S_1 = \left((\a+\b)(\a + \b\b)^*\b\a\right)^*$, then answer is that the automaton accepts

$$\left((\a+\b)(\a + \b\b)^*\b\a\right)^* (\epsilon + (\a+\b)(\a + \b\b)^*\b). $$

That first term, $\left((\a+\b)(\a + \b\b)^*\b\a\right)$, will always take the machine from the start state around the loop and back to the start state; after doing that some number of times, the machine can accept immediately (that's the $\epsilon$) or can proceed to state 3 via $(\a+\b)(\a + \b\b)^*\b)$.

share|cite|improve this answer
Nice exposition of the technique. – Brian M. Scott Aug 23 '13 at 17:28
Good job. You got the same answer as I did and saved me the trouble of writing it up (not to mention that my answer wouldn't have been as clear as yours). Congrats. – Rick Decker Aug 23 '13 at 17:40
Thanks! I attribute my success to my early decision to \def\a{\mathtt{a}}\def\b{\mathtt{b}}. – MJD Aug 23 '13 at 17:40
Thank you very much guys really. Can anyone share me links to such methods of conversion. – Evy Lino Aug 23 '13 at 17:42
The language $K^*L$ is always a solution to the equation $X = KX + L$, but it is the unique solution only if $1 \notin K$. If $1 \in K$, then all the languages of the form $K^*M$ where $M$ contains $L$ are also solutions. Fortunately, one can show that this situation never occurs when the algorithm nicely presented by MJD is used. – J.-E. Pin Aug 25 '13 at 8:30

MJD’s excellent answer illustrates a general technique for solving this sort of problem, but I think that it’s also worth pointing out what’s wrong with the regular expression that you got. The expression

$$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*a\Big)^*\tag{1}$$

captures every word that gets accepted at state $1$, and the expression

$$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*\Big)$$

captures everything that gets accepted at state $3$ without revisiting state $1$, so

$$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*a\Big)^*\Big(\big((a\cup b)a^*b\big)(ba^*b)^*\Big)\tag{2}$$

captures everything that gets accepted at state $3$. The union of $(1)$ and $(2)$ gives you what you want, and then an obvious application of distributivity lets you simplify it to

$$\Big(\big((a\cup b)a^*b\big)(ba^*b)^*a\Big)^*\Big(\epsilon\cup\big((a\cup b)a^*b\big)(ba^*b)^*\Big)\;.$$

Thus, you actually had all of the major pieces; you just didn’t put them together quite right.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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