search

caleb531 / automata

A Python library for simulating finite automata, pushdown automata, and Turing machines
https://caleb531.github.io/automata/
MIT License
347 stars 64 forks source link

Feature request: DFA Union, Intersection, Complement, etc. #24

Closed Tagl closed 3 years ago

Tagl commented 3 years ago

I would like to have operations like these implemented within the library. The most common operations used are probably:

Another useful operation would be checking for equivalence of two DFAs. If an equivalence check is added should the eq method be overloaded with the equivalence check? I'd like to open a discussion on what additional operations could be added to the library. I have implementations for all the listed operations in mind and I have already written code for the first three so I'll gladly add these operations myself.

caleb531 commented 3 years ago

@Tagl Answering these in FIFO order 😉:

  1. Those operations look good to me, if you're able to implement them (with the appropriate tests)
  2. I like the idea of an equality check, and would definitely like to override the equality operator (== / __eq__).
  3. We should also override other relevant operators, like:
    1. Union: | / __or__
    2. Intersection: & / __and__
    3. Concatenation: + / __add__
    4. Complement: ~ / __invert__
    5. Reverse: reversed() / __reversed__
    6. And of course, Equality: == / __eq__

Unfortunately, I don't think there's a practical operator to use for Kleene star, so I'd say just implement it as a method without any accompanying operator.

Feel free to submit me as many pull requests as you'd like as you implement operations. Again, adding tests are a requirement, but it will help you as much as it will help everyone else.

At any rate, thank you in advance for your willingness to contribute these operations!

Tagl commented 3 years ago

Concatenation, reverse and Kleene star are best implemented by utilizing NFAs so I'm gonna wait with those for a while.

Additional operations which I have implemented:

  1. Subset: <= / __le__ and < / __lt__ for proper subsets
  2. Superset: >= / __ge__ and > / __gt__ for proper supersets
  3. Difference: - / __sub__
  4. Symmetric difference: ^ / __xor__
  5. Is empty check, return True if the DFA has no final states after minimization
  6. Is disjoint check, returns True if the intersection of two DFAs is empty
  7. Is finite check, returns True if the DFA represents a finite language, False if infinite. Can be extended to enumeration/generation as well and possibly overload len for cardinality.

Should the naming follow the builtin set class with issubset or should it be is_subset?

caleb531 commented 3 years ago

@Tagl

Should the naming follow the builtin set class with issubset or should it be is_subset?

Definitely follow the builtin convention, i.e. issubset

Great work so far! Again, feel free to submit as many Pull Requests as you'd like! (with tests for your new operations, of course)

Tagl commented 3 years ago

First pull request (#28) is in, let me know if anything needs changing.

Tagl commented 3 years ago

I think it would be good to change the default behavior of minify to forget the original names and I would like to include that change with these operations. I think in most cases tracking states through their names is not very important. Suppose you calculate the union of multiple state machines (for example in my case I'm taking unions of hundreds of DFAs) then the state names will become quite large and will slow down everything for probably no reason. In the case that tracking them is desired then the methods can just be called with the retain_names parameter set to True

caleb531 commented 3 years ago

@Tagl That all sounds fine to me! I already merged your PR, which seemed to contain all of the operations we've discussed here. I'm going to keep this issue open, though, since we still have NFA operations (like concatenation and Kleene star) to implement.

I am now laying the groundwork (documentation and all) for an automata v5 release, which your DFA operation contributions will be part of. I will make sure to give you credit for your welcome contribution in my release notes!

caleb531 commented 3 years ago

@Tagl Would it be possible for you to write a test case that covers the following code in _has_cycle? That code is currently not covered by any existing tests. Please see my screenshots below.

The code in red never seemed to be hit my the tests.

Screen Shot 2021-03-20 at 3 30 36 PM

Screen Shot 2021-03-20 at 3 30 47 PM

Screen Shot 2021-03-20 at 3 31 04 PM

Tagl commented 3 years ago

The testcase that was supposed to cover this had 2 mistakes in it, I have fixed it and pushed.

caleb531 commented 3 years ago

@Tagl Thanks for that. I pulled down your code into my v5 branch. However, I did need to re-add your original test case in order to cover the if in _has_cycle. The code coverage is now at 100% again.

caleb531 commented 3 years ago

@Tagl I soon plan to publish the current operations you've implemented as part of a v4.1.0 release. Were you still planning to implement Kleene Star, Concatenation, and Reverse? Those appear to be the only operations which have not yet been implemented.

Tagl commented 3 years ago

@caleb531 Yes I did intend to add those, I'll get around to it in the next few days.

Tagl commented 3 years ago

@caleb531 I have submitted a PR (#38 ) which provides those operations.

caleb531 commented 3 years ago

Excellent, thank you, @Tagl! I will get to it within the next few days.

caleb531 commented 3 years ago

@Tagl I've reviewed your PR, and it looks very good! And I'll be happy to take care of updating the README with the documentation on these new operations.

Again, thank you so much! You have produced some really excellent work for this project. I plan to be releasing v5 very soon, at which point I will close this issue.

caleb531 commented 3 years ago

@Tagl And with that, I have just released Automata v5 with all the new operations you contributed! Thank you again!

https://github.com/caleb531/automata/releases/tag/v5.0.0