Design an algorithm to determine whether a finite automaton

Design an algorithm to determine whether a finite automaton accepts an infinite set. Prove that your algorithm is correct.

Solution

we will have M as the input for the finite automata.The algorithm to determine it accepts an infinite set is:

1.Firsly we will simulate M on all present strings of length between n and 2n-1 in which M has n states.

2.The second step gives output yes if and only if no string is accepted.

3.If not,then the output no.

This algrithm is true because:

1)The most important part is that this algorithm halts after a finite number of steps, and it is well specified.

2)Another important aspect about the correctness of the algorithm follows from the fact that if M accepts an infinite number of strings, it must accept one of length between n and 2n-1.