1. Problem 2: Make algorithm to convert NFA into regular expressions.
a) Implementation approach:
Turn NFA into GNFA, then remove the states and merge edge one-by-one.
b) The algorithm:
Step 1: Preprocess the NFA. Add a “S” state before the existing initial state as start state,
and start state jump to old initial state by ɛ; Add a “A” state after accept state as new accept
state, all old accept jump to A by ɛ.
Step 2: Create a matrix R to store the GNGA’s edge between state and state.
Step 3: Iterate matrix R to eliminates the state and merge the edges. In each iteration, we
point a state C that is nearest state “S”, then splice each of edge F that shot to C and each of
edge T that emit from C, and merge new edge to the edge between two state where F edge
from and where T edge to.
c) Some of the details:
The regular expression symbol priority is * > > , so if a “*” operation act on a multiple
char, we should put that in parentheses. When we do “ ” operate, if one side consists of
more than one character, we enclose it. On top of that, we need to avoid redundant
parentheses as much as possible.
d) Java program is :
package hwk2;
//import com.alibaba.fastjson.JSON;
public class Nfa2Re {
// Step1 : Add state S and State A to the formal NFA
public static String[] states = new String[] {"S","q1","q2","q3","q4","A"};
public static String[] tokens = new String[] {"0","1","e"};
public static String[][][] thegma = new String[][][] {
{
{},{},{"q1"},
