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!

Improve this question
$\endgroup$
7
  • $\begingroup$ Did you draw the transition table and try subset construction ? $\endgroup$
    – user93
    Jan 22, 2018 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, 2018 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, 2018 at 5:49
  • $\begingroup$ Nevertheless, it does not illustrate how to approach the problem I have. $\endgroup$
    – Googme
    Jan 22, 2018 at 6:11
  • $\begingroup$ The video provided in the link explains it in details $\endgroup$
    – user93
    Jan 22, 2018 at 6:34

1 Answer 1

Reset to default
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)$

Improve this answer
$\endgroup$
6
  • $\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, 2018 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, 2018 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, 2018 at 7:50
  • $\begingroup$ Yes. Solving is easier than creating the equations at start. $\endgroup$
    – wazdra
    Jan 22, 2018 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, 2018 at 8:20

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.