Prove or disporve the following Let D be a DFA with Q k if

Prove or disporve the following: Let D be a DFA with |Q| = k. if |L(D)| is finite then there exists a string w of length at most k-1 such that w is not an element of L(D)

Solution

Answer:

The given statement is false.

As a DFA with k states will accept all strings upto length k-1 , but it cannot accept k length string if the language of the DFA is finite.