How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent

Question

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

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!

Answer 1

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