kendall-hopkins/formal-theory

FormalTheory is a library that allows for manipulation and conversion of NFAs, DFAs and Regular Expressions.

1.0.0 2012-11-27 07:25 UTC

Requires

• php: >=5.3.0

MIT

• Kendall Hopkins

• state
• transform
• expression
• formal
• theory
• regex
• regular
• dfa
• nfa
• fa
• deterministic
• nondeterministic
• finite
• automata
• lexer
• optimizer

README

FormalTheory is a library that allows for manipulation and conversion of NFAs, DFAs and Regular Expressions. Some of the features it includes are:

• Regex Lexing (AST)
• Regex to NFA conversion
• NFA to DFA conversion (determinize)
• DFA minimization
• DFA solution counting
• FA equality
• FA superset/subset test
• FA proper superset/subset test
• FA has a valid solution
• FA print
• FA export as DOT
• FA string matching
• FA intersections
• FA unions
• FA negation
• FA reverse
• FA to Regex conversion (basic)
• Heavy Unit Test Coverage
• Modern Autoloading Support
• Regex optimization via rules

Note: FA is either a DFA or NFA

Coming Soon™

• Regex optimization via mutations
• Generalized DFA solving based on positive/negative match list