patternMinor
Condition for infinitude of the language of a finite state automaton
Viewed 0 times
infinitudetheconditionfinitelanguageforstateautomaton
Problem
There is a theorem which says that:
Given a finite state automaton having $n$ states, if there exists a string $w$ whose length satisfies $n \leq |w| \leq 2n-1$ then the language accepted by the automaton is infinite.
I understand the constraint $|w| \geq n$, but I don't understand why the constraint $|w| \leq 2n-1$ is there.
Given a finite state automaton having $n$ states, if there exists a string $w$ whose length satisfies $n \leq |w| \leq 2n-1$ then the language accepted by the automaton is infinite.
I understand the constraint $|w| \geq n$, but I don't understand why the constraint $|w| \leq 2n-1$ is there.
Solution
The additional condition allows you write a straight-forward algorithm -- check all strings with lengths in this interval -- for deciding (in)finiteness of the accepted language. Thus, you get a proof that this property is decidable (which it isn't for most automata models with super-regular power).
Context
StackExchange Computer Science Q#68610, answer score: 5
Revisions (0)
No revisions yet.