4
$\begingroup$

Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression?

NFA

The way I solved this problem is to first convert the NFA into a DFA using equivalent classes, and then proceed with the method described here. I feel in this case, that method is very inconvenient, as there are many loops and multiple accepting states. I wrote down all the partial regexps regarding to each accepting state alone, then unioned them together, then eliminated the redundant parts. My answer is $a(a^+ \cup b^*a \cup c^*)^+$.

I also tried to eliminate the $\varepsilon$ edges first then start from the "sanitized" NFA, but there were way too many edges in this case, and was very confusing during the process.

Edit: as @DavidRicherby has commented below, converting the NFA to DFA first is not necessary and makes the problem more complex.

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of How to convert finite automata to regular expressions? $\endgroup$ – David Richerby Sep 17 '18 at 14:10
  • 1
    $\begingroup$ Determinizing blows up the number of states exponentially, so is unlikely to be the best plan. $\endgroup$ – David Richerby Sep 17 '18 at 14:10
  • 1
    $\begingroup$ Hi @DavidRicherby, I do not think this is a duplicate. That question is a generic one. Although I have read through the answers there, I still have problems solving problems eg. this example involving multiple $\epsilon$ edges and accepting states. RandomPerfectHashFunction's answer below was very helpful. $\endgroup$ – John Sep 17 '18 at 18:50
3
$\begingroup$

State elimination method is a good technique, if used properly.

Solving $f_2$ can be done directly from the given automaton.
$$ f_2 = ( s \rightarrow q_1 \rightarrow f_2 + s \rightarrow q_2 \rightarrow f_2 + s \rightarrow f_1 \rightarrow f_2)^+ $$ ( Overall Kleene + due to $(f_2,\epsilon) \rightarrow s$) $$ f_2 = (a\cdot a^*\cdot a + a\cdot b^*\cdot a + (a\cdot c^*)^+\cdot c)^+ $$ This can be rearranged as $$ f_2 = (a\cdot a^+ + a\cdot b^*\cdot a + (a\cdot c^*)\cdot (a\cdot c^*)^*\cdot c )^+$$ $$ = ( a \cdot ( a^+ + b^*\cdot a + c^*\cdot (a\cdot c^*)^*\cdot c) )^+ $$
Similarly, $f_1$ can be solved directly from the given automaton as follows $$ f_1 = ( s \rightarrow q_1 \rightarrow f_2 \rightarrow s + s \rightarrow q_2 \rightarrow f_2 \rightarrow s)^* \cdot s \rightarrow f_1 \cdot (\epsilon + c \cdot \epsilon \cdot f_1) $$ $$ = ( a \cdot a^+ + a\cdot b^* \cdot a )^* \cdot (a\cdot c^*)^+ \cdot ( \epsilon + c \cdot \epsilon \cdot f_1) $$

$( \epsilon + c \cdot \epsilon \cdot f_1)$ represent the two possible transitions from $f_1$. If the input has been completed scanned, stop at $f_1$. If not, move to $f_2$ using $c$, then move to $s$ using $\epsilon$. Then start scanning for $f_1$ again.

This recursive relationship can be solved by taking $$ r = ( a \cdot a^+ + a\cdot b^* \cdot a )^* \cdot (a\cdot c^*)^+$$ Then $f_1$ becomes,

$$ f_1 = r \cdot ( \epsilon + c \cdot f_1)$$ $$ = r \cdot ( \epsilon + c \cdot ( r \cdot ( \epsilon + c \cdot f_1) ) )$$ Unravelling this recursion gives us, $$ f_1 = r + r \cdot c \cdot r + r \cdot c \cdot r \cdot c \cdot r + \space... $$ $$ = r \cdot ( c \cdot r )^*$$

$\endgroup$
  • 1
    $\begingroup$ Thank you for the answer! I am still a bit confused with the $f_1$ part, what does $\epsilon + c \cdot f_2$ represent at the end of that equation? Especially, what does $c \cdot f_2$ mean? (I understand the notation of eg. $s \rightarrow q_1$, but here $c$ is an edge/input/short hand of a transition function whereas $f_2$ is a state) $\endgroup$ – John Sep 17 '18 at 13:31
  • 1
    $\begingroup$ @John have made a mistake with $\epsilon + c \cdot f_2$. Let me correct it. $\endgroup$ – RandomPerfectHashFunction Sep 17 '18 at 13:40
  • 1
    $\begingroup$ @John I edited it a bit. I hope it seems clearer now. $\endgroup$ – RandomPerfectHashFunction Sep 17 '18 at 17:18
  • $\begingroup$ Ah I get it now! I didn't realize that this is meat to represent recursions. Thank you! $\endgroup$ – John Sep 17 '18 at 18:59

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.