RE2NFA2DFA2MFA
RE2NFA2DFA2MFA copied to clipboard
1. Use Thompson algorithm to convert the regular expression to NFA 2. Use the subset construct to convert NFA to DFA 3. Minimize DFA to MFA 4. Use MFA to match strings
RE--NFA--DFA--MFA
- Use Thompson algorithm to convert the regular expression to NFA
- Use the subset construct to convert NFA to DFA
- Minimize DFA to MFA
- Use MFA to match strings
How to run
src\main\test.java is the main funnciton.
Attention
Use an equal width font, otherwise the output table will not be aligned
Details
1. RE2NFA
-
NFA nfa = new NFA(re);
Creat a NFA by Thompson algorithm
-
nfa.add_join_symbol();
Add join symbol between regular expression
The join symbol is '.'
for example:
re = "(a|bc)*d";
re_add_join_symbol = "(a|b.c)*.d" ;
-
nfa.postfix();
Converts an infix expression to a postfix expression for example:
re_add_join_symbol = "(a|b.c)*.d";
re_postfix = "abc.|*d."
-
nfa.re2nfa();
Using Thompson algorithm constructs NFA
-
nfa.print();
Print out NFA (depth-first traversal)
2. NFA2DFA
-
DFA dfa = new DFA(nfa.getPair(),nfa.getLetter());
dfa.createDFA();
Construct the DFA using the subset construct
-
dfa.printDFA();
3. DFA2MFA
-
MFA mfa = new MFA(dfa.getDFA(),dfa.getEndState(),dfa.getLetter());
mfa.minimize();
Creat a MFA
-
mfa.merge();
merge
-
mfa.printMFA();