CMI2010-B-04a

Question

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

1. A DFA with $n$ states must accept at least one string of length greater than $n$.

Comments

To accept a language with - \[L = \left\{\epsilon: over \left\{a,b\right\}\right\}\]
 will have a DFA that will have two states but string length accepted by it is 0

Answer 1

FALSE.

It is true only if the DFA is accepting infinite set of strings. 

Say, the DFA accepts only $\mathbf{aa}$

Minimum number of states to accept $\mathbf{aa}$ is $4$ as shown below.

So, here no string with length $>4$ is accepted.

 

Comments

It will help I think. 

---

According to pumping lemma, if $xyz$ belongs to $L$ and $|w| > n$, where $n$ is a fixed constant for $L$, and $|xy| \leq n$ then $xy^iz \in L$ for $i \geq 0$.

What this means is that we have a min-DFA for $L$. And we are having a string whose length is sufficiently large to cause a loop in the DFA- without a loop the maximum length possible will be the longest path from start state to final state and that is $n$. So, once we have a loop for any string being accepted, we can repeat that loop any number of times (including removal of loop - or 0 times) and all the corresponding strings will be in $L$. This also implies that $L$ accepts infinite strings as $i$ can take any whole number.

Just putting $i = 2$ solves our problem for the given question.

---

https://gateoverflow.in/47073/cmi2010-b-04b

Here minimum longest path from start state to final state 2n

putting i=2 string length is 2n+y which is less than 3n . rt?