Regular Language Notation Language

Question

What I would like to do is design a program (for academic purposes) which will take a representation of a DFA (as a directed graph) and display the regular language which it accepts, in a reasonable format.

For example: For this graph: as input, an algorithm will spit out: a*b*

The set of regular languages is computable and decidable. But what about the language which we use to represent regular languages? Is it decidable as well?

Edit: I thought about this some more, and I think this should be doable, because implementation examples of regular expression parsers are bountiful, and clearly they internally construct a graph (or an equivalent structure). What I am wondering is if the reverse is possible -- construct the correct expression from a DFA representation.

Answer 1

First, you should use the algorithm which finds a minimal DFA. This can be done in polynomial time (squared, if I recall correctly) using an algorithm which separates states iteratively (in a way related to the Myhill-Nerod theorem). Second, just eliminate an unaccepting sink, if such exists (in the minimal automata, there can be at most one). Third, you can transform the DFA to an NFA working on regular expressions (edit: such a machine is called a GNFA), by chaining together (unaccepting) states, turning a self-loop to a star expression, and combining states going to the same state with the + operator. You would end up with a regular expression for the language.

However, the regular expression would not necessarily be minimal. Since a regular expression is closely related to the NFA representation, and finding a minimal NFA is a "hard" problem (unsolved yet in polynomial time), it would surprise me if such an algorithm exists.

Answer 2

By academic purposes do you mean you want to study the inner workings of such a program? If yes, go ahead.

If you just want a tool that converts DFAs to regular languages, you don't have to reinvent the wheel. The lecturer that teaches automata in our department uses JFLAP. I found it was easy to use and provided the needed functionality for accompanying a lecture.

You can find more information on the JFLAP homepage and yes, you can make alterations to it if you want to. It uses a custom license that allows expanding the tool.

Answer 3

The algorithm, by Kleene, to convert a DFA into a regular language that recognizes the same set is a variation on the Floyd-Warshall algorithm for all pairs shortest paths (and both are algebraically similar to Gaussian elimination).

The Kleene algorithm is described in Hopcroft, Ullman, Motwani in the chapter on equivalence of DFAs, NFAs, and regular expressions. A very general explanation of the process is at Floyd's algorithm for shortest paths.

Even though there is no concept really of shortest paths in a DFA, computing the language for all possible paths between two nodes in a DFA is very similar to find the shortest paths between such nodes (where the shortest 'weight' is the combination of languages along any path.