search

caleb531 / automata

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

More functionality for DPDA #102

Open Tagl opened 2 years ago

Tagl commented 2 years ago

My next focus was gonna be a little bit on DPDAs. I've started implementing enumeration and iteration. Are there any specific operations that you're particularly interested in prioritizing? Some of them may not have any known efficient algorithm (regularity of language) or may even be undecidable (although that's more common for the nondeterministic version). @caleb531 @eliotwrobson

Some ideas:

eliotwrobson commented 2 years ago

@Tagl I'm not an expert on these operations (my domain of knowledge and usage on stuff in the package is mostly limited to regular languages), but these all seem reasonable. I guess the operations with regular languages are the most interesting to me (due to what I said previously).

caleb531 commented 2 years ago

@Tagl Ideally, enumeration/iteration is something I'd personally love to see implemented for all automaton types. But I understand if we start running against the wall of feasibility.

Equivalence would also be great to have, but I understand if there are challenges with that. The order you listed other operations seems like a fine priority for me (e.g. care more about union than complement, and more about complement than emptiness).

caleb531 commented 2 years ago

@Tagl (cc @eliotwrobson) I think I'd actually like to save any DPDA work for a post-v7 release. I am starting to get eager to release v7 soon, with all of its substantial improvements to the library.

eliotwrobson commented 2 years ago

@caleb531 I'm inclined to agree. We've merged in a ton of changes that significantly overhaul large parts of the library. I think it would be good to release and get feedback on the existing changes.

Tagl commented 2 years ago

I think I'd actually like to save any DPDA work for a post-v7 release. I am starting to get eager to release v7 soon, with all of its substantial improvements to the library.

No worries, this is gonna take a long time.

eliotwrobson commented 1 year ago

Since there was mention of having the __iter__ working for all automaton types in the discussion here, I'll say that I'm not sure about any of the PDAs beyond the DPDA, but this is definitely infeasible for TMs (in fact, I don't think there are any nontrivial algorithms for TMs).

caleb531 commented 1 year ago

@eliotwrobson Just want to comment and say that's fine with me! If a feasible algorithm doesn't exist, then it is what it is.