# 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>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|. 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>2$$.