c01l/formal-theory

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

2.3.0 2021-11-10 15:03 UTC

Requires

• php: >=7.3

Requires (Dev)

• phpunit/phpunit: 9.5.10
• vimeo/psalm: ^4.11

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