Regular Expressions and Finite Automata (refa)

A library for regular expressions (RE) and finite automata (FA) in the context of Javascript RegExp.

About

This is a general library for DFA, NFA, and REs of formal regular languages.

It also supports additional methods to easily convert from JS RegExp to the internal RE ast and vice versa.

At this point in time, the library is still in development and partially incomplete!

Features

• Conversions

  • RE to NFA (lookarounds are not implemented yet)
  • NFA to DFA and DFA to NFA
  • NFA to RE and DFA to RE

• DFA and NFA operations

  • Construction from a finite set of words
  • Print internal representation in a human-readable form
  • Test whether a word is accepted
  • Test whether the language of an FA is the empty set
  • Test whether the language of an FA is a finite set

• DFA specific operations

  • Intersection with other DFA (not implemented yet)
  • DFA minimization
  • Complement
  • Structural equality

• NFA specific operations

  • Union and Intersection with other NFA
  • Concatenation with other NFA
  • Quantification

• Javascript RegExp

  • RegExp to RE and RE to RegExp

Limitations

This library will never be able to support some modern features of regex engines such as backreferences and recursion because these features, generally, cannot be be represented by a DFA or NFA.