contentking / FormalTheory Public

forked from witrin/FormalTheory

Notifications You must be signed in to change notification settings
Fork 1
Star 0

Regular Expression (Regex), Nondeterministic finite automaton (NFA) and Deterministic finite automaton (DFA) implement in PHP.

0 stars 4 forks Branches Tags Activity

Name		Name	Last commit message	Last commit date
Latest commit History 103 Commits
src		src
tests		tests
.travis.yml		.travis.yml
LICENSE		LICENSE
README.md		README.md
composer.json		composer.json
phpunit.xml.dist		phpunit.xml.dist

Repository files navigation

FormalTheory

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