Regular Expression (Regex), Nondeterministic finite automaton (NFA) and Deterministic finite automaton (DFA) implement in PHP. - Keywords: php php-library regex nfa dfa dfa-regex formal-languages

Kendall Hopkins 81f8957ee5 Remove extra newline 7 years ago
lib 81f8957ee5 Remove extra newline 7 years ago
test 8506a6e0ea Improve optimizer. 7 years ago
.travis.yml a98db5ab34 Change default support to UTF-8. 8 years ago
LICENSE 116c833aab Add LICENSE file. 7 years ago 25fa26a92a Implement FA reverse. 7 years ago
composer.json 9a3ff9f6fd Use correct name format. 7 years ago
phpunit.xml.dist eb20655eeb Add unit tests. 8 years ago


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

Build Status