1
$\begingroup$

I'm doing a problem where I need to prove that there is a language A ⊆ {0, 1}* with both of the following properties:

(i) For all x ∈ A, |x| ≤ 5.

(ii) Every DFA that decides A has more than 8 states.

To prove this, is it suffice enough to just give an example language A ⊆ {0, 1}* that holds both of these properties?

$\endgroup$
  • $\begingroup$ Yes, a given example proves that there is such an language. Does this answer your question? $\endgroup$ – Apass.Jack Feb 8 at 4:47
1
$\begingroup$

You can prove the existence of an object satisfying properties in many ways. The simplest is to exhibit such an object explicitly, which is what you can do in your case. But there are also other possibilities:

  1. Use a probabilistic argument. If you choose a uniformly random graph on $n$ vertices, then it will have no large clique or independent set. We don't know how to construct such graphs explicitly.

    Sometimes it is not enough to just choose a random graph. The well-known construction of graphs with high girth and high chromatic numbers modify a random graph so that it satisfies the requirements. A more sophisticated version is the recent interlacing polynomials method, used to construct Ramanujan graphs.

  2. Use a non-constructive argument. The is an algorithm that given $n$, determines whether the decimal expansion of $\pi$ contains a block of $n$ zeroes. Indeed, such a program either always returns YES, or it returns whether $n \leq N$, where $N$ is the longest such stretch of zeroes. While we do not at the moment know which of the two options is correct, one of them must be correct, and so the algorithm exists.

  3. Use a proof by compactness. Consider the problem of determining whether a graph can be embedded into a torus (without edge crossings). This is a minor-closed family of graphs, and we can consider the set of forbidden minors, i.e., minimal graphs (with respect to the minor relation) not embeddable into a torus. This is an antichain of graphs (with respect to the minor relation), so according to the graph minor theorem, it must be finite. Since we can test whether a graph on $n$ vertices has a given graph as a minor in time $O(n^2)$, it follows that we can determine whether a graph is embeddable in a torus in time $O(n^2)$. But we can't actually construct the algorithm, so we don't know the complete list of forbidden minors.

$\endgroup$

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.