Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states? Given an alphabet $\Sigma$, let $c=|\Sigma|$.  Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states?

I'm having trouble creating an $L_k$ such that any DFA for it has $\Omega(c^k)$ states.  There are constructions that require $\Theta(2^k)$ states, but here $c$ is an arbitrary constant, so if $c&gt;2$ those constructions do not suffice.



Is the language of strings with a suffix of $s_k, |s_k|=k$ such a language? Following is a draft proof of that.

Proof by contradiction: let a DFA $\langle Q, \Sigma, \delta, q_0, F\rangle$ have $|Q|&lt;c^{k-1}$. Let $a, b$ be strings of length $k$ and $a_k=(s_k)_1\not=b_k$

Let $q_a$ and $q_b$ denote $\delta(q_0, a)$ and $\delta(q_0, b)$, respectively.

There are two cases:

I. there are no $a,b$ such that $q_a=q_b$. Then each string corresponds to a different state, but there are $c^{k-1}$ such strings, therefore $|Q|\geq c^{k-1}$, which is not possilbe.

II. There are $a,b$ such that $q_a=q_b$. Then $\delta(q_a, s_2s_3\ldots s_k)=\delta(q_b, s_2s_3\ldots s_k)=q_c$. $as_2s_3\ldots s_k$ should be accepted and $bs_2s_3\ldots s_k$ shouldn't, therefore $q_c$ is both an accepting state and not an accepting state, which is not possible.

This seems to prove that any DFA for $L_k$ has at least $c^{k-1}$ nodes, which is sufficient for $\Omega(c^k)$. If my proof is correct, the only task left is to prove that a NFA containing $O(k)$ nodes exists for $L_k$.

The simplest way to do this is to create such a NFA, however I'm not sure how to do that. $O(k)$ suggests that $i$-th node should correspond to the state of "prefix of $s$ of length $i$ matches the suffix of the input string", however I do not follow how such a NFA can be created.
The language $L_k$ that you list doesn't work.

There is a straightforward NFA for the language $L_k$ you list, with $k+1$ states.  It guesses where the suffix starts, then checks that the suffix is equal to $s_k$.

In particular, the NFA has states $0,1,\dots,k$, with transitions $0 \to 0$ on each symbol, transitions $i-1 \to i$ on the symbol that matches the $i$th character of $s_k$, and $k$ being an accepting state.

It follows, using the subset construction, that there exists a DFA with $2^{k+1}$ states.

Consequently, that language does not meet your requirements, if $c&gt;2$.