Crate dandy

dandy

dandy is a Rust library for DFAs, NFAs, ε-NFAs and Regular Expressions, and an implementation of a file format for such. See the documentation for DFAs, NFAs and Regular Expressions for more detailed information about each data type and their operations

Usage

use dandy::dfa::Dfa;

let raw_dfa = "
       a  b  c
→ * s₀ s₁ s₀ s₂
    s₁ s₂ s₁ s₁
  * s₂ s₂ s₂ s₂
";
// First pass parses without checking validity of the DFA
let parsed_dfa = dandy::parser::dfa(raw_dfa).unwrap();
// Second step checks the existence of all mentioned states and
// the existence of an initial state
let dfa: Dfa = parsed_dfa.try_into().unwrap();
assert!(dfa.accepts(&["a", "b", "c", "c", "a"]));
assert!(dfa.accepts(&["c", "b", "a"]));
assert!(!dfa.accepts(&["a", "b", "b", "c"]));

let equivalent_dfa = "
    a b c
→ * x z x y
  * y y y y
    z y w z
    w y z w
";
let dfa2 = dandy::parser::dfa(equivalent_dfa).unwrap().try_into().unwrap();
assert!(dfa.equivalent_to(&dfa2));

File format

The file format used is more or less just a transition table. The first row (the header) should include the whole alphabet, and then the rest of the rows should consist of the states, one row for each state. The row should start with the state name and then, for each element of the alphabet, the transition from that state upon seeing that element. Before the state name, either -> or → should be used to denote the initial state, and * to denote that the state is accepting.

Example of a DFA:

       a  b  c
→ * s₀ s₁ s₀ s₂
    s₁ s₂ s₁ s₁
  * s₂ s₂ s₂ s₂

This table denotes an DFA accepting strings of the alphabet ‘a’, ‘b’, ‘c’ with either

• only ’b’s
• two ’a’s
• a ‘c’ before the first occurrence of ‘a’

Whitespace should be used for delimiters between →, *, the state name and the transition entries. Lines containing only whitespace will be ignored, and comments may be added using #, ignoring the rest of the row. Leading and trailing whitespace is ignored. The entries in the do not need to be aligned to the other rows or the alphabet.

To be a correctly denoted DFA, there must be a transition from each state for each alphabet element. All states referred to must be defined, and there must be exactly one initial state. There may also not be any duplicate elements of the alphabet.

The format for NFAs and ε-NFAs is very similar. For each state transition, a set of target states is denoted by {, then the states in a whitespace-separated list, and }. To define ε-transitions, the ε character should be added to the alphabet.

Example of an ε-NFA:

     ε    a       b
→ s₀ {}   {s₁}    {s₀ s₂}
  s₁ {s₂} {s₄}    {s₃}
  s₂ {}   {s₁ s₄} {s₃}
  s₃ {s₅} {s₄ s₅} {}
  s₄ {s₃} {}      {s₅}
* s₅ {}   {s₅}    {s₅}

Again, whitespace should be used for delimiters between →, *, the state name and the transition entries. Whitespace should also be used as a delimiter between entries in each set. Empty transitions (no transitions) must be written as the empty set {}. The same rules for comments and leading and trailing whitespace as for the DFAs apply. ε may be written as “eps”, and may be absent for denoting a non-ε-NFA.

Operations

This library currently supports, among other things:

• Parsing and validating DFAs
• Parsing and validating NFAs (with and without epsilon moves)
• Generating a table suitable for re-parsing of DFAs and NFAs
• Converting DFAs to NFAs, and NFAs to DFAs
• Checking whether two DFAs or two NFAs are equivalent
• Checking if a string is accepted by a DFA or NFA
• Step-by-step evaluation of a string
• Identifying and removing unreachable states from a DFA
• Identifying and merging non-distinguishable states from a DFA
• Minimizing a DFA (by executing the two above-mentioned steps)
• Product construction for DFAs, among union, intersection, difference and symmetric difference operations
• Product construction for NFAs
• Enumerating all words accepted by a NFA
• Removing epsilon moves from a NFA
• Parsing regular expressions
• Converting regular expressions to NFAs

See the documentation for DFAs, NFAs and Regular Expressions for more detailed information about each data type and their operations, together with some code examples

Modules

• dfa
  Deterministic Finite Automaton
• nfa
  Nondeterministic Finite Automaton, with our without ε-moves
• parser
  Parser for DFAs, NFAs and regular expressions
• regex
  Regular expressions