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

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

CC BY-SA 3.0
2016-04-30T16:51:59.510Z
2016-04-30T16:57:53.257Z
2016-04-30T16:57:53.257Z
StefanH
<p>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.</p>

CC BY-SA 3.0
2016-05-01T01:42:24.303Z
Take the transition matrix to powers n ... 2n. Accept state should be zero on all if the DFA only accepts finite strings.
Chad Brewbaker
<dfa>
How to check if a the language represented by a DFA is finite
Sayam Qazi
# How to check if a the language represented by a DFA is finite

(Asked by: username_0 on 2016-04-30)

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.

**Tags:** dfa
> **Comments:**
> **username_1**: Take the transition matrix to powers n ... 2n. Accept state should be zero on all if the DFA only accepts finite strings.  

---

## 1 answers

### Answer by username_2 on 2016-04-30. Score: 3 | Accepted answer

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.


---

