A language L is called regular iff it’s recognized by some NFA or DFA
If L has an NFA with $k$ states, that means L has a DFA with $2^k$ states.
Theorem: Define $\Sigma = {0,1}$
k = any positive integer
$L_k$ = {w: w has a 0 in kth position from end}
Then:
a) $L_k$ has an NFA of size k + 1
one loop state at the beginning, and k states to represent “kth from the end” and end is accept state
b) $L_k$ doesn’t have a DFA of size < $2^k$
proof: Let D be any DFA with < $2^k$ states
| Input | End state of D |
|---|---|
| 0.....00(length of k) | q27(arbitrary state ) |
| 0.....01 | q14 |
| .... | q114514 |
| 1......11(length of k) | q19 |
^ All $2^k$ strings of length K
End state of D can not be distinct since D has a size of < $2^k$
⇒ $\exists$ length-k strings u, v(u≠ v) such that
end state on u = end state on v
Say $u_i = 0$, $v_i = 1$ (since there must be something different about them)
⇒ End state on u concat with (i-1) 0s = end state on v concat with (i-1) 0s
^ has 0 in kth position from end ^ has 1 in kth position from end
Thus this D doesn’t recognize the language $L_k$