Skip to main content
Post Reopened by D.W.
added 165 characters in body; edited title; edited tags
Source Link
D.W.
  • 165.5k
  • 21
  • 230
  • 490

Does a set of formal languages exist Languages such that any DFA for it hasrequires $\Omega(c^k)$ states and there exists anbut NFA for it withneeds only $O(k)$ states?

Given an alphabet $\Sigma : |\Sigma|=c$$\Sigma$, canlet $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 athe 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.

Does a set of formal languages exist such that any DFA for it has $\Omega(c^k)$ states and there exists an NFA for it with $O(k)$ states?

Given an alphabet $\Sigma : |\Sigma|=c$, 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. Is a 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.

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

Post Closed as "Duplicate" by D.W.
Source Link
lsparki
  • 156
  • 6

Does a set of formal languages exist such that any DFA for it has $\Omega(c^k)$ states and there exists an NFA for it with $O(k)$ states?

Given an alphabet $\Sigma : |\Sigma|=c$, 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. Is a 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.