5
$\begingroup$

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

Example

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.

$\endgroup$
  • 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 '16 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$ – Captain Obvious Mar 13 '16 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 '16 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$ – Captain Obvious Mar 13 '16 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 '16 at 13:51
4
+50
$\begingroup$

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.

$\endgroup$
  • $\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$ – Captain Obvious Mar 15 '16 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$ – Captain Obvious Mar 15 '16 at 19:10
  • $\begingroup$ After trying the 3 algorithms, the only one that seems to work is the transitive closure method. $\endgroup$ – Captain Obvious Mar 17 '16 at 12:06
  • $\begingroup$ What do you mean by "seems to work"?? $\endgroup$ – J.-E. Pin Mar 17 '16 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$ – Captain Obvious Mar 17 '16 at 16:38

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.