CMI2019-A-2

Question

Let $A$ be an $NFA$ with $n$ states. Which of the following is necessarily true?

• A. The shortest word in $L(A)$ has length at most $n-1.$
• B. The shortest word in $L(A)$ has length at least $n.$
• C. The shortest word not in $L(A)$ has length at most $n-1.$
• D. The shortest word  not in $L(A)$ has length at least $n.$

Answer 1

Let us take an NFA with $3$ states i.e. $n=3$ as shown above. Also let $\Sigma = \{a,b\}$

A. The shortest word accepted is $aa$ and $|aa| =2 = n-1$  so option $A$ is true.

B. The shortest word accepted is $aa$ and $|aa| =2 = n-1$  so option $B$ is false.

D. The shortest word not is $L(A)$ is $\epsilon$ and $|\epsilon| = 0$  so option $C$ is false

Let us slightly update our NFA

C. The shortest word not accepted by this NFA is $aaa$ and $|aaa| = 3 = n $ so option C. is also false.

So option $A$ is the correct answer as it is the only argument that holds true for both cases.

 

 

 

 

Comments

option a must be true

Answer 2