I am studying regular languages and D FA. I have implemented D FA in Java. I have to write a function which tells if the language represented by a D FA is finite or not. I need a method or algorithm to do so. What I have already figured out is that if the D FA has loops in it then it can possibly recognize infinite words.


closed as off-topic by Emil Jeřábek supports Monica, user6973, Hsien-Chih Chang 張顯之, David Eppstein, Mohammad Al-Turkistany Apr 30 '16 at 18:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek supports Monica, Community, Hsien-Chih Chang 張顯之, David Eppstein, Mohammad Al-Turkistany
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Take the transition matrix to powers n ... 2n. Accept state should be zero on all if the DFA only accepts finite strings. $\endgroup$ – Chad Brewbaker May 1 '16 at 1:42

The language accepted by a deterministic finite automata is infinite if and only if there exists some cycle on some path from which a final state is reachable. If you minimize your automaton, then there is at most one state from where you cannot reach a final state anymore (a so called sink state). So algorithmically it is simply a check for each node if the set of final states is reachable, and if so if the resulting path has cycles in it.

For a proof, just note that if there are no cycles in an accepting path, there could be no repetition in the state sequence traversed by a word which is accepted, hence we could only decribe a finite number of words (more precisely $|Q|^d$, where $Q$ is the set of states and $d$ describes the length of a longest accepting path in the automata, is an upper bound for the distinct number of words that could be accepted). Otherwise, if we have cycles we could "pump" some accepted words, thus getting an infinite number of them.


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