snippetModerate
How to determine if an automata (DFA) accepts an infinite or finite language?
Viewed 0 times
dfaacceptsinfinitefiniteautomatalanguagedeterminehow
Problem
Given an automata [DFA $A=(Q,Σ,δ,q_0,F)$], is there a way to determine whether it accepts an infinite or finite language?
Solution
This is well enough known that you should be able to find it in most intro theory texts:
Theorem. The language accepted by a DFA $M$ with $n$ states is infinite if and only if $M$ accepts a string of length $k$, where $n\le k < 2n$.
This makes the decision problem simple: just try all strings of length at least $n$ and less than $2n$ and answer "yes" if $M$ accepts one of them and "no" if there's no string in that range that's accepted.
Theorem. The language accepted by a DFA $M$ with $n$ states is infinite if and only if $M$ accepts a string of length $k$, where $n\le k < 2n$.
This makes the decision problem simple: just try all strings of length at least $n$ and less than $2n$ and answer "yes" if $M$ accepts one of them and "no" if there's no string in that range that's accepted.
Context
StackExchange Computer Science Q#73993, answer score: 15
Revisions (0)
No revisions yet.