1
$\begingroup$

Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form:

enter image description here

To a regular expression equivalent. What I have tried was using arden's rule. However I just cant figure out how to simplify and return the appropriate regular expression corresponding to that NFA.

First I have created the initial equation corresponding to those states:

$1: q3 = q_1 0 + q_1 1$

$2: q1 = q_0 0 + q_1 1$

$3: q0 = q_0 0 + q_0 1 + \epsilon$

Which I have tried to simplify:

$1: q3 = (q_0 0 + q_1 1)0 + (q_0 0 + q_1)1$

$1: q3 = q_0 00 + q_1 100 + q_0 01 + q_1 11$

$1: q3 = q_0(0+1) + q_1(0+1)$

$2: q1 = q_0 00 + q_0 10 + \epsilon 0 + q_0 01 + q_1 11$

$2: q1 = q_0(0+0+1)+ \epsilon 0 + q_1 11$

$3: q0 = q_0 0 + q_0 1 + \epsilon$

$3: q0 = q_0(0+1) + \epsilon$

Here I just lost. Maybe there is a different approach suitable in this context.

Appreciate any help!

$\endgroup$
  • $\begingroup$ Did you draw the transition table and try subset construction ? $\endgroup$ – user93 Jan 22 '18 at 5:21
  • $\begingroup$ Hi yes, I think your example is not correct since if you convert that NFA to DFA it will have multiple final states. $\endgroup$ – Googme Jan 22 '18 at 5:42
  • $\begingroup$ I used your nfa diagram to draw the transition table and use subset construction to get the dfa. nfa to dfa does not always need to have multiple final states $\endgroup$ – user93 Jan 22 '18 at 5:49
  • $\begingroup$ Nevertheless, it does not illustrate how to approach the problem I have. $\endgroup$ – Googme Jan 22 '18 at 6:11
  • $\begingroup$ The video provided in the link explains it in details $\endgroup$ – user93 Jan 22 '18 at 6:34
1
$\begingroup$

The Arden's rule, as it is usually stated, is easier to use if you consider equations on $(L_q)_{q\in Q}$ depicting the language $L_q$ the automaton accepts from state $q$. Doing this, you obtain the following equations. Check that you understand this properly :

  • $L_0 = 0L_0 + 1L_0 + 0L_1$
  • $L_1 = 0L_3 + 1L_3$
  • $L_3 = \varepsilon$

(I use $L$ instead of $q$ as it looks less misleading to me)

Once you have those equations, you can solve this as follows

  • $L_1 = 0 + 1$ (I replaced $L_3$ with its value)
  • $L_0 = (0+1)L_0 + 0(0+1)$ (Replaced $L_1$ and factorized. This is ready for Arden's rule)
  • Since $\epsilon\not\in L_0$, from Arden's rule : $L_0 = (0+1)^*0(0+1)$

The language accepted by the automaton is always the union of the $L_{q_i}$, where the $q_i$ are the initial states. So here, $L = L_0 = (0+1)^*0(0+1)$

$\endgroup$
  • $\begingroup$ Hi wazdra, is there a way you could show me how to solve them since thats where Im struggling at $\endgroup$ – Googme Jan 22 '18 at 7:38
  • $\begingroup$ Did you understand how I got the equations ? I solve them right underneath. If you are talking about your equations, those are really not suited for Arden's rule $\endgroup$ – wazdra Jan 22 '18 at 7:41
  • $\begingroup$ Hmm Im not 100% sure, you are saying that the regular expression corresponding to that NFA in my example is (0+1)*0(0+1)? $\endgroup$ – Googme Jan 22 '18 at 7:50
  • $\begingroup$ Yes. Solving is easier than creating the equations at start. $\endgroup$ – wazdra Jan 22 '18 at 7:59
  • 1
    $\begingroup$ Yes, $L_3$ corresponds to the language this automaton would accept if you started from $q_3$. Since $q_3$ is an accepting state, you would accept e. Since there is no transition out of $q_3$, this is all you can accept. So $L_3 = e$. $\endgroup$ – wazdra Jan 22 '18 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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