dictomaton VS myrex

Say you want to compute all strings of length 5 that the automaton can generate. Conceptually the nicest way is to create an automaton that matches any five characters and then compute the intersection between that automaton and the regex automaton. Then you can generate all the strings in the intersection automaton. Of course, IRL, you wouldn't actually generate the intersection (you can easily do this on the fly), but you get the idea.

Automata are really a lost art in modern natural language processing. We used to do things like store a large vocabulary in an deterministic acyclic minimized automaton (nice and compact, so-called dictionary automaton). And then to find, say all words within Levenshtein distance 2 of hacker, create a Levenshtein automaton for hacker and then compute (on the fly) the intersection between the Levenshtein automaton and the dictionary automaton. The language of the automaton is then all words within the intersection automaton.

I wrote a Java package a decade ago that implements some of this stuff:

https://github.com/danieldk/dictomaton

Also related: Levenshtein automata - automata for words that match every word within a given Levenshtein distance. The intersection of a Levenshtein automaton of a word and a DAWG gives you an automaton of all words within the given edit distance.

I haven't done any Java in years, but I made a Java package in 2013 that supports: DAWGs, Levenshtein automata and perfect hash automata:

https://github.com/danieldk/dictomaton

Concurrent parallel execution of NFA directly in Elixir:

https://github.com/mike-french/myrex

It is concurrent in both senses: a single match is split into many concurrent traversals of the network; multiple input strings can be matched concurrently within the same network; generators can also run concurrently in the network. It's possible because all state is in the traversal messages, not in the process nodes, and the whole thing runs asynch (non-blocking) in parallel, automatically using all cores in the machine.

> you see how regex syntax compiles down to various configurations of automata

That is Thompson's Construction [1]. The Myrex README contains a long description of how regex structures map to small process networks, and how they glue together. The final process network is a direct 1-1 representation of the NFA.

[1] Russ Cox has a nice explanation https://swtch.com/~rsc/regexp/regexp1.html

Another interesting question is: how many possible successful matches are there for a given input string. For example:

How many ways can (a?){m}(a){m} match the string* a{m}

i.e. input is m repetitions of the letter 'a'.

https://github.com/mike-french/myrex#ambiguous-example

This is Thompson's Construction.

There is a nice description given by Russ Cox:

https://swtch.com/~rsc/regexp/regexp1.html

This project has an interesting implementation in Elixir, which converts the NFA directy into a process network:

https://github.com/mike-french/myrex

The network runs all possible traversals concurrently, and automatically scales to use all cores (Erlang BEAM runtime). Multiple input strings can also be processed concurrenty. It can also generate matching strings concurrently (Monte Carlo). It implements captures and Unicode character sets.

While it is designed for concurrency, it is not meant to be the fastest regex implementation. There is an example of a highly ambiguous match that launches 900k traversals and reports all capture results in about 10s.