-2
$\begingroup$

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:enter image description here

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Anwar
    Commented May 1, 2022 at 11:26
  • $\begingroup$ @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? $\endgroup$
    – Pratik Hadawale
    Commented May 1, 2022 at 11:38
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ashkan Khademian
    Commented May 1, 2022 at 15:57
  • $\begingroup$ 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. $\endgroup$
    – Pratik Hadawale
    Commented May 1, 2022 at 16:33

1 Answer 1

Reset to default
0
$\begingroup$

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 :)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ah, i should have worked at it more. Thank You for typing all of that out, this is exactly what i was looking for :) $\endgroup$
    – Pratik Hadawale
    Commented May 1, 2022 at 13:20
  • $\begingroup$ Glad to help :) $\endgroup$
    – Anwar
    Commented May 1, 2022 at 13:32

Your Answer

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

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