states
is a utility program for working with deterministic finite-state
automata (DFA), non-deterministic finite-state automata (NFA) and regular
expressions.
Planned features include:
- converting between NFA, DFA and regular expressions
- checking if a give string is accepted by the given NFA/DFA/regex (so it can be used like grep)
- incrementally finding all strings accepted by the given NFA/DFA/regex
- performing various operations on NFA/DFA/regex such as union, intersection, concatenation and Kleene closure
- supporting a nice syntax for representing NFA/DFA/regex
- exporting NFA/DFA/regex to TikZ and other formats
- minimize DFA
- diff the languages of two NFA/DFA/regex
- count how many strings are accepted of a give length
Some of these features have already been implemented.
$ ./autogen.sh
$ ./configure
$ make
# make install
The following example shows how states
can read an NFA and then incrementally
output all strings that are accepted by it.
$ cd examples
$ cat nfa.st
$ lang a-b | states nfa.st | head -n 20
$ cat re.st
$ lang a-b | states re.st | head -n 20