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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.