Skip to content

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

License

Notifications You must be signed in to change notification settings

Solawhite/RE2NFA2DFA2MFA

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

RE--NFA--DFA--MFA

  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

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."

avatar


  • nfa.re2nfa();
    Using Thompson algorithm constructs NFA

  • nfa.print();
    Print out NFA (depth-first traversal)

avatar avatar

2. NFA2DFA

  • DFA dfa = new DFA(nfa.getPair(),nfa.getLetter());
    dfa.createDFA();
    Construct the DFA using the subset construct

  • dfa.printDFA();
    avatar

3. DFA2MFA

  • MFA mfa = new MFA(dfa.getDFA(),dfa.getEndState(),dfa.getLetter());
    mfa.minimize();
    Creat a MFA

  • mfa.merge();
    merge

  • mfa.printMFA();
    avatar

4. Match

avatar

About

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

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages