-4
$\begingroup$

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.

$\endgroup$
  • $\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
1
$\begingroup$

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.

$\endgroup$

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