Skip to content

Feature request: Closure operations #15

Open
@ksf

Description

@ksf

Regular languages are closed under complement, intersection, union and difference (because they're sets) as well as under reversal, it would be great to have those available as they provide much expressive and combinatorial power, intersection probably being the one with most practical use.

Complement is trivial on a DFA, just switch all final states to non-final and vice versa.

Union already exists in the guise of alternation, intersection follows by De Morgan's Law, difference is (intersect a (not b), reversal is reversing all edges of an DFA and switching start and end states (you end up with an NFA, then)

...that's not to say that I think it's trivial to do, though. Doing them on graph-based automata would be two hours worth of work, implementing them for online automata is a different kind of beast.

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions