Converting an NFA to an equivalent Regular Expression - the GNFA method

The GNFA method is a procedure to convert any given NFA to an equivalent regular expression. The idea is to rip out one state at a time, while modifying the transitions to reflect the changes. Here is an example explaining the process in detail

NFA

Consider the following NFA

State $\downarrow$ Transition $\rightarrow$	$a$	$b$	$c$
$q_0$ – start, final	$q_1$	$q_2$	$q_2$
$q_1$ – final	$q_2$	$q_1$	$q_0$
$q_2$	$q_2$	$q_0$	$q_0$

This can be expressed as the following state transition diagram

Rendered by QuickLaTeX.com

Adding start and final states

The first step is to add a new start and a single new final state. The new start state is labeled as $s$ . The new start state has an $\epsilon$ transition to the original start state of the NFA. The new final state is labeled as $f$ . All the final state(s) in the original NFA have an $\epsilon$ transition to the new final state. The two new additions are marked in color.

Rendered by QuickLaTeX.com

Every state except $s$ and $f$ needs to ripped out. The order of choosing a state to rip out doesn’t really matter.

Rip $q_2$

Consider the state $q_2$ . The incoming (blue), looping (orange) and outgoing (green) transitions for this state are marked in different colors.

Rendered by QuickLaTeX.com

Thus, there are two paths through $q_2$ . This is summarized below

Path	Incoming	Loop	Outgoing
$q_0 - q_2 - q_0$	$b \cup c$	$a$	$b \cup c$
$q_1 - q_2 - q_0$	$a$	$a$	$b \cup c$

To rip state $q_2$ , the transitions along these paths need to accounted for. The equivalent transition is defined as

$\begin{equation*} (\text{Incoming}) \cdot (\text{Loop})^* \cdot (\text{Outgoing}) \end{equation*}$

Applying this to the table above

Path	Incoming	Loop	Outgoing	Equivalent Transition
$q_0 - q_2 - q_0$	$b \cup c$	$a$	$b \cup c$	$R_1 = (b \cup c) (a)^* (b \cup c)$
$q_1 - q_2 - q_0$	$a$	$a$	$b \cup c$	$R_2 = (a) (a)^* (b \cup c)$

After ripping the state $q_2$ the NFA changes to the following

Rendered by QuickLaTeX.com

Rip $q_1$

Consider the state $q_1$ . The incoming (blue), looping (orange) and outgoing (green) transitions for this state are marked in different colors.

Rendered by QuickLaTeX.com

Thus, there are two paths through $q_1$ . This is summarized below

Path	Incoming	Loop	Outgoing
$q_0 - q_1 - q_0$	$a$	$b$	$c \cup R_2$
$q_0 - q_1 - f$	$a$	$b$	$\epsilon$

To rip state $q_1$ , the transitions along these paths need to accounted for. The equivalent transition is defined as

$\begin{equation*} (\text{Incoming}) \cdot (\text{Loop})^* \cdot (\text{Outgoing}) \end{equation*}$

Applying this to the table above

Path	Incoming	Loop	Outgoing	Equivalent Transition
$q_0 - q_1 - q_0$	$a$	$b$	$c \cup R_2$	$R_3 = (a) (b)^* (c \cup R_2)$
$q_0 - q_1 - f$	$a$	$b$	$\epsilon$	$R_4 = (a) (b)^* (\epsilon)$

After ripping the state $q_1$ the NFA changes to the following

Rendered by QuickLaTeX.com

Rip $q_0$

Consider the state $q_0$ . The incoming (blue), looping (orange) and outgoing (green) transitions for this state are marked in different colors.

Rendered by QuickLaTeX.com

Thus, there is one path through $q_0$ . This is summarized below

Path	Incoming	Loop	Outgoing
$s - q_0 - f$	$\epsilon$	$R_1 \cup R_3$	$\epsilon \cup R_4$

To rip state $q_0$ , the transitions along these paths need to accounted for. The equivalent transition is defined as

$\begin{equation*} (\text{Incoming}) \cdot (\text{Loop})^* \cdot (\text{Outgoing}) \end{equation*}$

Applying this to the table above

Path	Incoming	Loop	Outgoing	Equivalent Transition
$s - q_0 - f$	$\epsilon$	$R_1 \cup R_3$	$\epsilon \cup R_4$	$R_5 = (\epsilon) (R_1 \cup R_3)^* (\epsilon \cup R_4)$

After ripping the state $q_0$ the NFA changes to the following

Regular Expression

The equivalent regular expression is the transition from $s$ to $f$ .

$\begin{align*} R_5 &= (\epsilon) (R_1 \cup R_3)^* (\epsilon \cup R_4) \\ &= (R_1 \cup R_3)^* (\epsilon \cup R_4) \\ &= (R_1 \cup R_3)^* (\epsilon \cup (a) (b)^* (\epsilon)) \\ &= (R_1 \cup R_3)^* (\epsilon \cup ab^*) \\ &= (R_1 \cup ((a) (b)^* (c \cup R_2)))^* (\epsilon \cup ab^*) \\ &= (R_1 \cup (ab^* (c \cup R_2)))^* (\epsilon \cup ab^*) \\ &= (R_1 \cup (ab^* (c \cup (a) (a)^* (b \cup c))))^* (\epsilon \cup ab^*) \\ &= (R_1 \cup (ab^* (c \cup aa^* (b \cup c))))^* (\epsilon \cup ab^*) \\ &= ((b \cup c) (a)^* (b \cup c) \cup (ab^* (c \cup aa^* (b \cup c))))^* (\epsilon \cup ab^*) \\ &= ((b \cup c) a^* (b \cup c) \cup (ab^* (c \cup aa^* (b \cup c))))^* (\epsilon \cup ab^*) \\ \end{align*}$

Depending on the order of ripping out states, the NFA may be converted to different equivalent regular expressions.

The Beard Sage

Converting an NFA to an equivalent Regular Expression – the GNFA method

NFA

Adding start and final states

Rip $q_2$

Rip $q_1$

Rip $q_0$

Regular Expression

Leave a Reply Cancel reply