CMI2010-B-04b

Question

Indicate whether the following statement is true or false, providing a short explanation to substantiate your answers.

A DFA that has $n$ states and accepts an infinite language must accept at least one string $x$ such that $2n < |x| < 3n$, where $|x|$ denotes the length of $x$.

Comments

Can any one please look into this again , check if it is correct or not.

According to me , if we consider even length strings over {a} then there will be 2 states in DFA.

Hence 2n<|w|<3n ==> 4<|w|<6  and it is not possible to have any string of length between 4 and 6 for DFA which accepts even length string.

As per me it is False, Please provide explanation if it is True.

---

@thebiggercypher your logic seems correct.

Answer 1

FALSE.

DFA has $n$ states and so the smallest length string accepted will be $< n.$ Let its length be $d.$

Now, since infinite strings are accepted we must have a loop in the DFA. the length of the loop will be $\leq n$ because we only have $n$ states. Let this loop length be $l.$

So, strings of length $d, d+l, d+2l, d+3l, \ldots, d+nl, d+(n+1)l, \ldots$ will be accepted by the DFA.
At some point in the above sequence, the string length will cross $2n$. Lets take the string length just before this such that $|x| \leq 2n$ and $| x|+ l > 2n.$

Since, $l \leq n, |x| + l \leq 2n + n \leq 3n.$

So, the DFA must accept at least one string $x$ such that $2n < |x| \leq 3n.$

This can also be $2n \leq |x| < 3n.$

Since the given question says $2n <|x| < 3n$ it is FALSE. We can prove this with a small counter example as shown below. 

The above DFA accepts all even length strings of over the alphabet set $\{a\}$ and its number of states is $2$. But no string is accepted of length between $2n$ and $3n$ which will be $4$ and $6.$

Comments

@Arjun Sir. The question doesn't talk about max number of final states in the DFA under consideration. So in your even length DFA example, I can consider both states as final state and then it will accept string of length 0,1,2,3,4,5....so here string of length between 2n adn 3n is accepted! Can you clarify on this?

---

Excellent answer Sir.

But There are some technicalities here. 

 DFA has n states and so the smallest length string accepted will be <n. Let its length be d.

The smallest length string is, not necessarily, eligible to be the string to start with. 

Since DFA accepts Infinite language so there must be at least one final state which accepts infinite strings. Let $F$ be any such final state. Since $F$ accepts infinite strings, there must be at least one path $P$ from starting state to it which is the base of some loop. So, there are infinite walks from starting state to $F$ going through this Pathway (by repeating that loop whose base path $P$ was). Now, by the theorem/result "Every Walk has a Path", we can say that there is at least one simple path from starting state to $F$ and so some string of length less than $n$ is accepted by $F$ along this path $P.$   This is the string to start with. So, this is the string whose length you have taken $d.$ 

---

Moreover, by similar argument you gave in the answer, we can also say that there will be some strings $x_i$ such that 

$n < | x_1| \leq 2n$  and $2n < | x_2| \leq 3n$ and $3n < | x_3| \leq 4n$ and so on...

And there will be some strings $y_i$ such that 

$n \leq | y_1| < 2n$  and $2n \leq | y_2| < 3n$ and $3n \leq | y_3| < 4n$ and so on...

 

 

---

A much simpler (and a bit hackish) answer would be a DFA with 1 state, basically a universal acceptor. For that the |w| would have to lie b/w 2 and 3 and |w| is an integer. Contradiction. So, False.

Answer 2

Consider above DFA in which:

$\text{initial state} = q0$

$\text{final states} = \{q0,q1\}$

$\text{trap sate} = q2$

Language generated by above DFA is $a^*b^*$ which is an infinite language

$n= 3$ (number of states)

now consider $\text{string} \ X=\{aaabbbb\}$ i.e., $a^3b^4$   

$|X| = 7$

now $2n= 2*3 = 6$

$3n = 3*3 = 9$

$2n<|x|<3n \Rightarrow 6< 7 <9 $

 

Hence, it is proved.

Comments

In general, if there is a language accepting strings of length in multiple of n then DFA would be having n states accepting strings of length 0, n, 2n, 3n and so on...

Clearly there won't be any string of length between 2n & 3n acceptable to DFA.

The statement seems to be false.

---

If we can prove the statement to be false for atleast one case then it is considered false. 

The given statement can be proved false for the DFA accepting even length strings. Thus, the given statement should be false. @ Tauhin Gangwar please correct me if I am wrong.

---

Correct. there might be many DFAs in which condition 2n<= |x| <= 3n holds true but bcz it is not set fit for all DFAs hence the statement is False.

Answer 3

Answer: FALSE

Comments

Yes, I am getting similar kind of result. Please can someone confirm once ?

---

i think you are right as if it is true then it should hold for every DFA which accepts infinite language.

Answer 4

Pumping Lemma for the regular languages say

Now the point is there will be at least one string w such that $\left | w \right |$ is less than n.
Proof: Take the shortest path from the initial state to the final state in the DFA having n state.

Now as pumping lemma said, for any w $\in$ L. We will choose our w in such a way that $\left | w \right |$ < n and we decomposed into w = xyz, satisfying the condition given in pumping lemma.

$w_{i}$ = x$y^{^{i}}$z . whenever we increment 'i' by 1. The length of the string can't be increased by n as $\left | y \right |$ is not greater than n. Therefore we will get at least one string say 's' whose length is between n and 2n, between 2n and 3n, between 3n and 4n and so on.
 

Comments

should be selected as best answer

---

w is split into xyz if |w|>=n. In case where x and z are zero y^2 will give string of length 2n and if y<n then we will get string lengths of length <2n. Same holds true when we pump more ys.

so n<=|x|<=2n

  2n<=|x|<=3n.... and so on

---

@Hemant Parihar: For pumping lemma to work |w| >= n and not < n.

We can then decompose w = xyz where |xy| <= n and |y| >= 1.

Here in this case we choose w to be anything in [n, 2n). So that we can decompose w as

w = xyz where we choose |x| = 1, |z| = 1,so |y| <= n-1. This gives |xy| <= n.

We can now pump y in x y^i z once, twice, and so on.

Pumping y once for i = 2 insures we have a string w in (2n, 3n) as |y| <= n-1 so pumping once can't add a multiple of n.