PHPackages                             witrin/formal-theory - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Parsing & Serialization](/categories/parsing)
4. /
5. witrin/formal-theory

ActiveLibrary[Parsing & Serialization](/categories/parsing)

witrin/formal-theory
====================

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

1.1.0(9y ago)118.6k1MITPHPPHP >=5.3.0

Since Nov 26Pushed 9y ago2 watchersCompare

[ Source](https://github.com/witrin/FormalTheory)[ Packagist](https://packagist.org/packages/witrin/formal-theory)[ Docs](https://github.com/witrin/FormalTheory)[ RSS](/packages/witrin-formal-theory/feed)WikiDiscussions master Synced 1mo ago

READMEChangelog (1)DependenciesVersions (2)Used By (0)

FormalTheory
============

[](#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

[![Build Status](https://camo.githubusercontent.com/f44be30f2744015abbcec26493b066b82ff4cc55cb521581e168fbd983b94595/68747470733a2f2f7365637572652e7472617669732d63692e6f72672f4b656e64616c6c486f706b696e732f466f726d616c5468656f72792e706e673f6272616e63683d6d6173746572)](http://travis-ci.org/KendallHopkins/FormalTheory)

###  Health Score

30

—

LowBetter than 65% of packages

Maintenance20

Infrequent updates — may be unmaintained

Popularity22

Limited adoption so far

Community9

Small or concentrated contributor base

Maturity58

Maturing project, gaining track record

 Bus Factor1

Top contributor holds 100% of commits — single point of failure

How is this calculated?**Maintenance (25%)** — Last commit recency, latest release date, and issue-to-star ratio. Uses a 2-year decay window.

**Popularity (30%)** — Total and monthly downloads, GitHub stars, and forks. Logarithmic scaling prevents top-heavy scores.

**Community (15%)** — Contributors, dependents, forks, watchers, and maintainers. Measures real ecosystem engagement.

**Maturity (30%)** — Project age, version count, PHP version support, and release stability.

###  Release Activity

Cadence

Unknown

Total

1

Last Release

3452d ago

### Community

Maintainers

![](https://www.gravatar.com/avatar/77d406174e7255ee445e75d8fc4dee543e657eb164b5e1df2b28c6ca0fdc1da8?d=identicon)[witrin](/maintainers/witrin)

---

Top Contributors

[![KendallHopkins](https://avatars.githubusercontent.com/u/72923?v=4)](https://github.com/KendallHopkins "KendallHopkins (99 commits)")

---

Tags

lexerstateexpressionregexregulartransformfiniteoptimizerdeterministicformaltheorydfanfafanondeterministicautomata

### Embed Badge

![Health badge](/badges/witrin-formal-theory/health.svg)

```
[![Health](https://phpackages.com/badges/witrin-formal-theory/health.svg)](https://phpackages.com/packages/witrin-formal-theory)
```

###  Alternatives

[kendall-hopkins/formal-theory

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

335.4k](/packages/kendall-hopkins-formal-theory)[doctrine/lexer

PHP Doctrine Lexer parser library that can be used in Top-Down, Recursive Descent Parsers.

11.2k910.8M118](/packages/doctrine-lexer)[spatie/regex

A sane interface for php's built in preg\_\* functions

1.1k17.1M59](/packages/spatie-regex)[cerbero/json-parser

Zero-dependencies pull parser to read large JSON from any source in a memory-efficient way.

803474.6k5](/packages/cerbero-json-parser)[rawr/t-regx

PHP regular expression brought up to modern standards.

451157.3k3](/packages/rawr-t-regx)[nxp/math-executor

Simple math expressions calculator

2281.7M7](/packages/nxp-math-executor)

PHPackages © 2026

[Directory](/)[Categories](/categories)[Trending](/trending)[Changelog](/changelog)[Analyze](/analyze)