GATE 2011
November 4, 2024Probability
November 6, 2024CMI 2019
|
Question 2
|
Let A be an NFA with n states. Which of the following is necessarily true?
|
The shortest word in L(A) has length at most n-1.
|
|
|
The shortest word in L(A) has length at least n.
|
|
|
The shortest word not in L(A) has length at most n-1.
|
|
|
The shortest word not in L(A) has length at least n.
|
Question 2 Explanation:
Assume that L(A) is non-empty. If A accepts a word of length >= n, there is an accepting run of A that has at least one loop. If we cut out all the loops in this run, we get an accepting run (on some other word) that visits each of the n states at most
once, and hence there are at most n-1 transitions, meaning there is a word in L(A) of length at most n-1. Thus the shortest word in L(A) has length at most n-1.
once, and hence there are at most n-1 transitions, meaning there is a word in L(A) of length at most n-1. Thus the shortest word in L(A) has length at most n-1.
Correct Answer: A
Question 2 Explanation:
Assume that L(A) is non-empty. If A accepts a word of length >= n, there is an accepting run of A that has at least one loop. If we cut out all the loops in this run, we get an accepting run (on some other word) that visits each of the n states at most
once, and hence there are at most n-1 transitions, meaning there is a word in L(A) of length at most n-1. Thus the shortest word in L(A) has length at most n-1.
once, and hence there are at most n-1 transitions, meaning there is a word in L(A) of length at most n-1. Thus the shortest word in L(A) has length at most n-1.