701607be-2c9c-4f1e-9069-e5945d2c495d
commented
1 year ago Been thinking a bit about this ticket. The reversal procedure in the referenced document (i.e. DFA(->NFA)->RE->reverse, then back) would work, but is probably harder than it needs to be, and would require implementing a Regular Expression class.
Furthermore, in its current implementation, the automaton class represents NFAs, of which DFAs are effectively a subset, and the .determinisation() method allows for a standard NFA->DFA conversion.
Inverting NFAs is more or less trivial, and I'm going to try and implement something for it now.
In short, we can invert DFAs by treating them as NFAs, inverting them, then calling the .determinisation() method.
As far as I'm aware, sage currently has no regular expression type, and conversion between NFAs and Regular Expressions is possible, but quite hard to do by hand, so I think if anything that could be more useful. It would also lead to another (albeit probably worse) way of inverting automata but that's besides the point.
I'm wondering if anyone thinks it might be worth making a ticket for the implementation of a regular expression class, for nothing else if not providing a fast way for converting between NFAs and regular expressions.
The code for it already exists
https://stackoverflow.com/questions/17983289/how-can-i-convert-a-regex-to-an-nfa https://www.ics.uci.edu/~eppstein/PADS/Automata.py
dimpase
Deterministic Finite Automata are closed under reversal. The FiniteStateMachine class has several closure operations implemented that the Automaton class inherits, but not reversal. This patch would add the reversal closure operation to the Automaton class.
See: http://infolab.stanford.edu/~ullman/ialc/spr10/slides/rs2.pdf
Component: finite state machines
Keywords: Finite State Machines, Closure Properties, Automata
Issue created by migration from https://trac.sagemath.org/ticket/19924