v6.0.0

Automata v6 is a major new release with new features and a few breaking changes that keep the library moving forward. Big thanks to @abhinavsinha-adrino and @eliotwrobson for most of these improvements.

New Features

• A new GNFA class to represent generalized non-deterministic finite automata (thanks @abhinavsinha-adrino!)
  • Please see the README for documentation on this new class
• A new automata.base.regex module with utilities for working with
  automata-style regular expressions; a new NFA.to_regex method has also been added
  • Please see the README for documentation on this new module
• A new NFA.eliminate_lambda method to return an NFA with lambda/epsilon
  transitions removed (#31)
• Significant performance optimizations to various DFA methods (thanks
  @eliotwrobson!):
  • DFA.from_nfa
  • DFA.isempty
  • DFA.isfinite
  • DFA.__eq__

Breaking Changes

• Added networkx as a required dependency, providing substantial performance improvements for certain DFA/NFA methods, and also streamlining the code to improve maintainability
• Dropped Python 3.6 support, since it has been end-of-life since December 2021. Python 3.7 is currently the minimum version of Python required by this library.

Bug Fixes

• Fixed a bug with NFA.kleene_star() where outgoing transitions for every final state were required (but shouldn't be)
• Fixed a bug where the DFA union and intersection operations were not returning the correct type if you had subclassed from DFA

v5.0.0

Automata v5 is a major new release with new goodies and also some backwards-incompatible changes:

New Features

New DFA/NFA Operations

• Added a plethora of new DFA and NFA operations (big thanks to @Tagl for contributing!); please see the README for documentation on all new methods/operators:
  • DFA Operations
    • Empty check (dfa1.isempty())
    • Finite check (dfa1.isfinite())
    • Disjoint check (dfa1.isdisjoint(dfa2))
    • Subset check (dfa1 <= dfa2)
    • Superset check (dfa1 >= dfa2)
    • Strict subset check (dfa1 < dfa2)
    • Strict superset check (dfa1 > dfa2)
    • Equivalence check (dfa1 == dfa2)
    • Complement (~dfa1)
    • Union (dfa1 | dfa2)
    • Intersection (dfa1 & dfa2)
    • Set difference (dfa1 - dfa2)
    • Symmetric difference (dfa1 ^ dfa2)
  • NFA Operations
    • Reversal (reversed(nfa1))
    • Concatenation (nfa1 + nfa2)
    • Kleene Star (nfa1.kleene_star())
• Added new visualization capability for DFAs using pydot (thanks to @lewiuberg)
  • Please note that pydot is now a dependency of this library
  • To use, call the DFA show_diagram() method; see the README for usage
  • On macOS, run brew install gprof2dot to allow pydot to function fully

Breaking Changes

• Dropped Python 3.5 support, since it has been end-of-life since
  September 2020. Python 3.6 is now the minimum supported version of Python.
• Added pydot as a required dependency (per the new visualization feature below)
• No backwards-incompatible API changes otherwise

Flag to Enable Partial DFAs

• Added an allow_partial parameter for DFAs that permits a state to not have transitions for every input symbol; see the README for usage (#36)

Other improvements

• Improved the performance of the DFA.minify() method
• Improved handling of automata with non-string state names (i.e. an InvalidStateError is no longer raised)

v4.0.0

• Dropped support for Python 3.4 because it has reached end-of-life
• There have been no API changes from v3 to v4 otherwise

v3.1.0

New Features

• Added a new (optional) acceptance_mode parameter for DPDAs and NPDAs. Accepted values are 'final_state', 'empty_stack', or 'both'; the default value is 'both'

v3.0.0

New Features

• Added a new NPDA class for nondeterministic pushdown automata

  • A new PDAConfiguration class has also been added, which is immutable and hashable; it is essentially a tuple of state, remaining input, and stack

• Added a new NTM class for nondeterministic Turing machines

  • A new TMConfiguration class has also been added, which is immutable and hashable; it is essentially a tuple of state and tape

• Added N direction for DTM and NTM to indicate no tape movement

Breaking changes

• PDAStack is now immutable and hashable; it still represents the current stack of a PDA
• TMTape is now immutable and hashable; it still represents the tape of a TM and the current cursor position
• The copy methods on TMTape and PDAStack have been removed, since they are now immutable types

v2.1.0

• Added a new minify() method for DFAs, which removes unreachable states and merges equivalent states

v2.0.1

• Refactored DFA.from_nfa() to improve its efficiency and handle more complex cases (thanks @YtvwlD)
• Added __init__.py to every module to improve compatibility with interpreters like bpython (also @YtvwlD)

v2.0.0

• Automata v2 introduces a number of backwards-incompatible API changes to clean up and improve the API
  • Please see the Migration Guide for a detailed overview of these changes
• Added a new input method, accepts_input(), which returns a boolean
  • For more details, see the README

v1.0.0-rev.3

• Included all sub-packages in PyPI distribution

v1.0.0-rev.2

• Rebuilt the .egg-info file with the compiled reST README (for the PyPI project page)