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