Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA

  • some nodes have multiple in/outgoing edges

  • single start state

  • there might be multiple final states

  • a state can contain self loops where a symbol is consumed
  • no epsilon transitions


What i'm trying to do is generate a regular expression from this graph. I've found the following topic using Brzozowski algebraic method: https://cs.stackexchange.com/q/2392

However, it seems to be for DFA's, so my question:

can I use Brzozowski algebraic method OR Transitive closure method with my NFA, or do i need conversion first?

I need an algorithm that can be done by a computer to automatically generate a regex from a given graph.

  • 5
    $\begingroup$ Have you looked at the method? Does is rely on determinism anywhere? Some of the other methods at that question you link are explicitly said to work for nondeterministic automata. $\endgroup$
    – Raphael
    Mar 12, 2016 at 16:49
  • $\begingroup$ Your method is for NFA's yes, but i need an algorithm to solve it computationally, without "prolog style" languages. The other methods do not state anything about whether they are suitable for NFA or not, or am i overlooking things? $\endgroup$ Mar 13, 2016 at 11:19
  • $\begingroup$ Well, maybe the authors did not feel the need to state anything explicitly, which would indicate that NFAs work as input. Have you looked at the methods? Try to find out for yourself? Do the methods need determinism at any time? $\endgroup$
    – Raphael
    Mar 13, 2016 at 17:50
  • 1
    $\begingroup$ Hey Raphael, thanks for your time. Yes, I did look at them and I don't see anything special that might fail the algorithm, but in the end I'm not sure and searching google didn't really help me to validate that it can be applied to an NFA. In some cases my graph is a DFA, but sometimes I have 2 edges with the same symbol, i.e. 2 choices instead of 1 which makes it an NFA. Any clarification is appreciated if i'm wrong $\endgroup$ Mar 13, 2016 at 18:37
  • 1
    $\begingroup$ You can not "assume" anything. You can check and make sure, i.e. prove what you need. I did not look at the methods closely myself, so I can not say one or the other with certainty. $\endgroup$
    – Raphael
    Mar 15, 2016 at 13:51

1 Answer 1


Brzozowski's algebraic method is safe as long as you don't have epsilon transitions. It even works if your transitions are labelled by languages not containing the empty word. It may also work if some transitions contain the empty word, as long as you can eliminate them, as in the example below: enter image description here

the system can be written as \begin{align*} X_1 &= (a^*b + a)X_2 + b^*X_3 \\ X_2 &= (a+b)X_1 + bX_3 + 1 \\ X_3 &= aX_1 + aX_2 + 1 \end{align*} Replacing $X_3$ by $aX_1 + aX_2 + 1$, and observing that $a + b^*a = b^*a$, we obtain the equivalent system \begin{align*} X_1 &= (a^*b + a)X_2 + b^*(aX_1 + aX_2 + 1) = b^*aX_1 + (a^*b + b^*a)X_2 + b^* \\ X_2 &= (a+b)X_1 + b(aX_1 + aX_2 + 1) + 1 = (a + b + ba)X_1 + baX_2 + b + 1\\ X_3 &= aX_1 + aX_2 + 1 \end{align*} We deduce from the second equation $$ X_2 = (ba)^*((a + b + ba)X_1 + b + 1) $$ and replacing $X_2$ by its value in the first equation, we obtain \begin{align*} X_1 &= b^*aX_1 + (a^*b + b^*a)(ba)^*((a + b + ba)X_1 + b + 1) + b^*\\ &= (b^*a + (a^*b + b^*a)(ba)^*(a + b + ba))X_1 + (a^*b + b^*a)(ba)^*(b + 1) + b^* \end{align*} Finally, the language recognised by the automaton is $$ X_1 = \bigl(b^*a + (a^*b + b^*a)(ba)^*(a + b + ba)\bigr)^*[(a^*b + b^*a)(ba)^*(b + 1) + b^*] $$ since $1$ is the unique initial state.

Now, if you want to implement this algorithm, you may end up with more complicated regular expressions. For instance, the sentence "observing that $a + b^*a = b^*a$" might be difficult to implement. Other useful simplifications like $a^* + 1 = a^*$ or even $K + K = K$ or $K + L = L + K$, where $K$ and $L$ are regular expressions, are also not easy to implement and require more sophisticated rewriting systems.

  • $\begingroup$ Thank you very much, i will check it out soon. Do you also know whether the Transitive closure method is applicable to NFA's? $\endgroup$ Mar 15, 2016 at 18:37
  • $\begingroup$ I've updated my post, with my NFA, just to make sure i'm not making mistakes. Also do you think the algorithm at the referred post: cs.stackexchange.com/a/2392/47780, is correct? Can you explain it by any chance? $\endgroup$ Mar 15, 2016 at 19:10
  • $\begingroup$ After trying the 3 algorithms, the only one that seems to work is the transitive closure method. $\endgroup$ Mar 17, 2016 at 12:06
  • $\begingroup$ What do you mean by "seems to work"?? $\endgroup$
    – J.-E. Pin
    Mar 17, 2016 at 14:47
  • $\begingroup$ I've implemented the pseudo-codes and manually examined the results, and the only one that worked was the transitive closure method. Possibly the pseudo-code of Brzozowski's algorithm is not correct, or do you think it is? $\endgroup$ Mar 17, 2016 at 16:38

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.