HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Condition for infinitude of the language of a finite state automaton

Submitted by: @import:stackexchange-cs··
0
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.

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.