9
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

In the worst-case scenario, your NFA could look like this:

The smallest $w$ for which it is guaranteed to loop (forcing it to accept an infinite language) has size $2n-1$.

$\endgroup$
  • $\begingroup$ When i start from q0 and after then when i came back at q0,that means there is a cycle in the machine. Isn't it sufficient thing in worst case,why are we going back to final stage again in this case?As far as i understand from this figure ,that we will pump this loop once and then go to final stage again,so it means once we enter in final stage then we are assuming that this is not my string as it went back to some other state,but once it comes back to final stage again,then we are sure that this our string as there is some loop that has been pumped? $\endgroup$ – rahul sharma Jan 13 '17 at 1:59
  • $\begingroup$ We are trying to prove something about the automaton, namely, that it accepts an infinite language. In the way the proof is formulated, a string $w$ is conjectured, whose size is assumed to be within a certain interval. Obviously, if the automaton has a loop, then the string $w$ exists. What happens is that if $w$ is impossible to find inside this interval, then the machine cannot be like the one in the picture. Either it has no loops, or it has no final states. $\endgroup$ – André Souza Lemos Jan 13 '17 at 3:09
  • $\begingroup$ I understand your point.I am just trying to understand the upper bound on the interval,why it is 2n-1 and why not 2n-x(x can be anything except 1).In the figure above can we are saying loop is qo-q1....qn-q1....qn,right(the max. loop)?But when i am q0 again(q0...aq,q0) ,doesn't it means that there is a loop,so maximum should be n,why are we adding n-1 to n(or why are we going to final state again).I am having some hard time in getting this:(. can max. loop be q0.,q1,q2..qn,qn-1,qn-1..q0,something like that? $\endgroup$ – rahul sharma Jan 13 '17 at 4:26
  • $\begingroup$ The upper bound is $2n-1$ because it doesn't get worse than that. $2n-x$ is smaller than $2n-1$, and I just showed you an automaton that needs $2n-1$ steps. There isn't one that needs more (and does the job), but there is one that needs this amount. $\endgroup$ – André Souza Lemos Jan 13 '17 at 4:32
  • $\begingroup$ Got it now.Just one small doubt.Assume i have 4 states in my machine.And i read string abc and i reached final state and then i read d there and came back to initial state,and then goes to final state again,so my string will become abcdabc. How can i break this into pumping lemma ,and get y^i,where i=1,to show that y has been pumped once.? $\endgroup$ – rahul sharma Jan 13 '17 at 5:03
5
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

The full theorem states an equivalence rather than an implication:

The language accepted by an $n$-state NFA is infinite if and only if it contains a word $w$ whose size satisfies $n \leq |w| \leq 2n-1$.

The extra condition $|w| \leq 2n-1$ thus makes the theorem stronger.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.