# How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?

Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method

I end up with this:

My question is, is there a way to cross verify that my E-NFA accepts the language of Regular expression mentioned at the start in this post? I tried converting the Resultant E-NFA back to Regular Expression using Arden's Theorem. But I end up with a inifite substitution for the final state q9

Also, is my constructed E-NFA correct?

EDIT: Adding Converting "resultant E-NFA to RE"

epsilon transition = e

q1 = e

q2 = q1e + q8e

q3 = q2e

q4 = q3a

q5 = q4b

q6 = q2e

q7 = q6a

q8 = q7e

q9 = q8e + q1e

Since we have to final states, q1 and q9 we need to substitue other values in q1 and q9. We will start with q9

q9 = q8e + q1e

q9 = q7ee + e

q9 = q6aee + e

q9 = q2eaee + e

q9 = (q1e + q8e)eaee + e

q9 = q1eeaee + q8eeaee + e

q9 = q1a + q8a + e

We again got q8, so this chain will always repeat. So what do i do from here?

• Yes your answer is correct, trying some strings in language ($\varepsilon$,$a$,$ab$,$aa$,$abab$,$aab$,$aba$,...) should give a strong intuition about its correctness, to be certain surely reconverting it back to a Regular expression is good, if you have a problem maybe modify your question to add a picture of your conversion attempt, although trying some inputs on a small NFA like this should probably suffice Commented May 1, 2022 at 11:26
• @Moslem I have added the "conversion that i tried" as an EDIT, it would be great if you have a look at it. Also one more question, whether the start state will be accept state <- this can easily be decided by just looking the RE and seeing if the Regular Expression can result into string of length 0 right? Commented May 1, 2022 at 11:38
• I think this is a question-and-answer site, so we require you to articulate a concrete question. Our questions need to help future works but this question seems a college task to me. Commented May 1, 2022 at 15:57
• Oh it isn't a college task, may be the way i wrote the title and content made it seem like that. I just used that Regular Expression as an example, i was more interested in "cross verifying" and to do that the best way is to solving using example. Commented May 1, 2022 at 16:33

You should try the substitutions in order so that you don't get a loop, here is the solution

$$q1 = \varepsilon$$

$$q_2 = q_1 \varepsilon + q_8 \varepsilon$$

$$q_3 = q_2 \varepsilon$$

$$q_4 = q_3a$$

$$q_5 = q_4b$$

$$q_6 = q_2 \varepsilon$$

$$q_7 = q_6a$$

$$q_8 = q5 \varepsilon + q_6 \varepsilon$$

$$q_9 = q_8 \varepsilon + q1 \varepsilon$$

Substitute for $$q_1 = \varepsilon$$ in every other rule

$$q_2 = \varepsilon \varepsilon + q_8 \varepsilon = \varepsilon + q_8 \varepsilon$$

$$q_3 = q_2 \varepsilon$$

$$q_4 = q_3a$$

$$q_5 = q_4b$$

$$q_6 = q_2 \varepsilon$$

$$q_7 = q_6a$$

$$q_8 = q5 \varepsilon + q_6 \varepsilon$$

$$q_9 = q_8 \varepsilon + \varepsilon \varepsilon = q_8 \varepsilon + \varepsilon$$

Substitute for $$q_2 = \varepsilon + q_8 \varepsilon$$ in every other rule

$$q_3 = (\varepsilon + q_8 \varepsilon) \varepsilon = \varepsilon + q_8 \varepsilon$$

$$q_4 = q_3a$$

$$q_5 = q_4b$$

$$q_6 = (\varepsilon + q_8 \varepsilon) \varepsilon = \varepsilon + q_8 \varepsilon$$

$$q_7 = q_6a$$

$$q_8 = q5 \varepsilon + q_6 \varepsilon$$

$$q_9 = q_8 \varepsilon + \varepsilon$$

Substitute for $$q_3 = \varepsilon + q_8 \varepsilon$$ in every other rule

$$q_4 = (\varepsilon + q_8 \varepsilon)a = a + q_8a$$

$$q_5 = q_4b$$

$$q_6 = \varepsilon + q_8 \varepsilon$$

$$q_7 = q_6a$$

$$q_8 = q5 \varepsilon + q_6 \varepsilon$$

$$q_9 = q_8 \varepsilon + \varepsilon$$

Substitute for $$q_4 = a + q_8a$$ in every other rule

$$q_5 = (a + q_8a)b = ab + q_8ab$$

$$q_6 = \varepsilon + q_8 \varepsilon$$

$$q_7 = q_6a$$

$$q_8 = q5 \varepsilon + q_6 \varepsilon$$

$$q_9 = q_8 \varepsilon + \varepsilon$$

Substitute for $$q_5 = ab + q_8ab$$ in every other rule

$$q_6 = \varepsilon + q_8 \varepsilon$$

$$q_7 = q_6a$$

$$q_8 = (ab + q_8ab) \varepsilon + q_7 \varepsilon = ab + q_8ab + q_7 \varepsilon$$

$$q_9 = q_8 \varepsilon + \varepsilon$$

Substitute for $$q_6 = \varepsilon + q_8 \varepsilon$$ in every other rule

$$q_7 = (\varepsilon + q_8 \varepsilon)a = a + q_8 a$$

$$q_8 = ab + q_8ab + q_7 \varepsilon$$

$$q_9 = q_8 \varepsilon + \varepsilon$$

Substitute for $$q_7 = a + q_8 a$$ in every other rule

$$q_8 = ab + q_8ab + (a + q_8 a) \varepsilon = ab + q_8 ab + a + q_8 a = a + ab + q_8(a+ab)$$

Now we can apply Arden's Theroem

$$q_8 = a + ab + (a+ab)^* = (a+ab)^*$$

$$q_9 = q_8 \varepsilon + \varepsilon$$

Substitute for $$q_8 = a + (ab)^*$$

$$q_9 = (a+ab)^* \varepsilon + \varepsilon = (a+ab)^*$$

And here is our solution :)

• Ah, i should have worked at it more. Thank You for typing all of that out, this is exactly what i was looking for :) Commented May 1, 2022 at 13:20
• Glad to help :) Commented May 1, 2022 at 13:32