Condition for regular language to be infinite

Question

Given M = (Q,Σ,δ,q0,F) a DFA with n states. Prove:
The language L(M) is infinite iff it contains a string with length t, where n ≤ t < 2n.
Please provide a prove. I am not getting it from the resources available on the net.
Why isn’t the criteria like n ≤ t only ?
When there are n states and if we get strings of length greater than equal to n that means DFA must have a loop. With a loop in DFA we can accept infinite no. of strings isn’t it? Then why doesn’t this condition suffice?

Please point out where I am going wrong.

Comments

Please point out where I am going wrong.

no where you are wrong !, you are absolutely right, let L = ∑*, then given statement is false.

 

the sentence would be like :

The language L(M) is infinite if it contains a string with length t, where n ≤ t < 2n.

it is correct !

---

@Shaik Masthan

But there is some reason behind this upper bound 2n. I don't get it :(

 

---

brother, upper bound should be n ≤ t for your statement.... check with any example, you will get it

---

The DFA should be minimal DFA

---

sir, didn't get you...

let RL = { ∈, a,aa,aaa,.....} = a*   on input alphabet ∑ = { a }

then only one state is sufficient to represent this language... and that is minimal DFA

So, the given statement condition evaluates as 1 ≤ t < 2.

But my string let aaaa ===> t = 4, then the given condition is fails

---

@Arjun

sir, can you help on this https://gateoverflow.in/272643 ?

otherwise i have to remember it as a formula..

---

@Shaik Masthan

See these:

https://cs.stackexchange.com/questions/73993/how-to-determine-if-an-automatadfa-accepts-an-infinite-or-finite-language

https://gateoverflow.in/104257/toc-finite-automata-infinite-language

http://infolab.stanford.edu/~ullman/ialc/spr10/slides/rs1.pdf (From Page 20)

@Arjun Sir, in the last reference that I attached, they said that

"There are an infinite number of strings of length>n, we can't test them all" and hence gave that upper bound of 2n. Please help me here. Why can't we just check for cycles in the DFA to determine it? Why do we have to go through all the strings of length>n when only testing for length=n can do?

 

 

---

@Shaik Masthan 

https://gateoverflow.in/263964/gatebook-2019-toc1-7

@MiNiPanda Please ping me next week if you dont get it. I'll explain. 

---

 @MiNiPanda, Ther is a reason for this upper bound $2n$.
See how I understand this statement-

When there are n states and if we get strings of length greater than equal to n that means DFA must have a loop. With a loop in DFA we can accept infinite no. of strings isn’t it? 

Yes, But we need to find a string of length at least $n$ to prove that there is a loop/cycle present so our language is infinite.
Now the problem is how can we find this string $w$. There is an infinite number of strings of length $\geq n$ and it might be possible that some of them are not there in the language.
For example- if the language is a*b then $aaaaa...n+1 \ times$ won't be there in $L$.

We need to find an upper bound on the number of strings to check before we can tell that L is infinite or not. 

Suppose there is a loop on all $n$ states. 
On the path from initial to final state, take the $1^{st}$ round of all the loops. You will get a string of length at most $2n-1$. 
Now for getting the string of length $2n$, you must have to take at least 1 loop twice.
So there must be a string in L which can be obtained if you that that loop only once.

In short, from the strings of length $2n$, we need to take at least 1 loop twice. So will always get a shorter string by just taking that loop once :)

---

@Soumya29,

Thank you so much for this..can you please clarify this one as well..

Since lower bound is n, we can enumerate all the strings of length "n" which will be a finite set of strings and check if our DFA accepts it or not. This will reduce our time from checking infinite strings. Now the mistake that I am doing here is, the DFA might not be accepting any string of length n and may accept strings of length=n+1. Like for eg: a DFA accepting strings of form $(00)^{+}$ . This DFA will have 3 states and a loop from final state to the middle state. So in order to say the language is infinite, according to lower bound, I will be checking if DFA accepts strings of length 3. But the DFA won't accept strings of length 3 and wrongly I will conclude that language is finite though it accepts strings of length 4,6,8...

Now possible length of cycles in the DFA that can accept strings of various lengths are:

1. 0 (no cycle) .. DFA accepts strings of length= (n-1)

2. 1 (cycle on FINAL state) .. DFA accepts string of length= (n-1)+1 = n [Obv DFA will accept strings of other lengths as well but here I am considering the minimum length using the cycle for once]

3. 2 (cycle from final state to 2nd last state i.e. state coming before the final ) .. DFA accepts string of length= (n-1)+2 = n+1

4. 3 (cycle from final state to 3rd last state ) .. DFA accepts string of length= (n-1)+3 = n+2

5. This continues until there is a cycle from final to initial state.. then it will be nth last state (i.e. the 1st state) so DFA accepts string of length= (n-1)+n = 2n-1

This will be the max length of cycle that a DFA can have. This sets the upper bound.

Please correct me if you find any glitch in this alternate approach.

Thank you.

---

@MiNiPanda, Yes it looks fine to me.
We just need to check all possible strings $w$ such that $n \leq |w| < 2n$, one by one. If our DFA accepts one of them, we will stop there and say that our language is infinite. 
If DFA accepts no such string then we will say that our language is finite. 

The crux is - whatever possible combination of loops and cycle we try, we have to take at least 1 of them twice to get a string of length $\geq 2n.$

---

Yes.. once again thank you so much @Soumya29 😋