Feature request for a regex inverse command

[Darkmatterg7]

Given a DFA saved in the library, please make a command that outputs the regular expression for the DFA.

[shallit43]

There is not "the" regular expression. There is no notion of canonical regular expression for a DFA. There are a variety of DFA to regular expression algorithms, but none of them are likely to be useful except for very very small DFA's.

[shallit43]

An example of why I think this should be a low priority action item: consider the 8-state automaton that accepts even numbers in Fibonacci representation. In Walnut it is the extremely simple

msd_fib

0 1
0 -> 0
1 -> 1

1 0
0 -> 2

2 1
0 -> 3
1 -> 4

3 0
0 -> 5
1 -> 6

4 1
0 -> 3

5 0
0 -> 2
1 -> 7

6 1
0 -> 0

7 0
0 -> 5

Now let's find a regular expression for it, using the Grail package. I cannot conceive that anyone would have the slightest benefit from knowing that a regular expression for it is

and on and on like this for 3 more screensful. (I had to use an image because annoyingly this comment feature does not allow one to use the symbol * for Kleene closure without messing stuff up.)

[jn1z]

If you can find another library that outputs regexes and supports BA format, you can try the following:

export my_automaton BA;

This will export the my_automaton automaton to BA format, which is fairly well supported (used in SPOT, RABIT, AutomataLib, FORKLIFT, ROLL 1.0, etc.)

[shallit43]

It's a little weird, though, since the automata Walnut uses aren't Buchi automata. I imagine one would have to be careful, because the regular expression for Buchi automata wouldn't be the same as if you consider it an ordinary automaton. The regular expression for Buchi automata would contain things like "omega" in the exponent, for example.

[jn1z]

That's a good point. The format is usually used interchangeably with finite and Buchi automata (usually by specifying a "--finite" argument somewhere), but it would be easy to get unexpected results here.