Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

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: 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.

share|improve this question
I'm not completely sure about the correct notation, but isn't the language accepted by the DFA in your example $a^*b^+a\lbrace a,b\rbrace ^*$? – Abel Mar 31 '11 at 7:29
@Abel: Not quite. The DFAs accepting states are only state 1 and state 2. Therefore, ba will not be accepted (because it ends up in state 3), although your regular expression accepts it. a*b* is the correct regular expression for this DFA. – Zach Langley Apr 1 '11 at 0:42
@Zach: Oh, you're right. – Abel Apr 1 '11 at 1:26
1  
There is not necessarily a unique correct regular expression for a given language. For example, a*a*b*b* = a*b*. Which one do you choose? – Raphael Apr 1 '11 at 20:28

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
1  
finding the minimal DFA is just for having the output depend only on the language. It is unnecessary for the actual transformation. elimination of non-accepting sink is necessary for the process to finish (otherwise you get stuck with more than one state - because you can't eliminate a non-accepting sink). Of course, you are correct about the terminology. I just didn't remember the exact name. – yaakov Apr 1 '11 at 11:55
First, in the minimal DFA there can be only one such state. Second, it is quite easy to detect - simply check for each state if there is an accepting reachable state (can be done in linear time). – yaakov Apr 3 '11 at 18:57
no, linear is enough, since there is no need to revisit nodes which you assured already that an accepting state is reachable from them. – yaakov Apr 3 '11 at 20:37
up vote 3 down vote

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.

share|improve this answer
up vote 1 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.