This is an exercise from Introduction to Languages and the Theory of Computation, by John Martin.

Suppose $L$ is a language over $\Sigma$, and $x_1, x_2, ... , x_n$ are strings that are pairwise $L$-distinguishable. How many distinct strings are necessary in order to distinguish between the $x_i$'s? In other words, what is the smallest number $k$ such that for some set $\{z_1, z_2, ...,z_k\}$, any two distinct $x_i$'s are distinguished, relative to $L$, by some $z_l$? Prove your answer.

The book gives a hint, which reads as follows:

Here is a way of thinking about the question that may make it easier. Think of the $x_i$’s as points on a piece of paper, and think of the $z_l$’s as cans of paint, each $z_l$ representing a different primary color. Saying that $z_l$ distinguishes $x_i$ and $x_j$ means that one of those two points is colored with that primary color and the other isn’t. We allow a single point to have more than one primary color applied to it, and we assume that two distinct combinations of primary colors produce different resulting colors. Then the question is, how many different primary colors are needed in order to color the points so that no two points end up the same color?

Here is my response to the coloring question

Solution: Coloring $n$ points so that no two points end up the same color requires $\lceil \log_2 n \rceil$ primary colors.

First enumerate the points using binary representations, and let each digit correspond to a primary color. Then we identify the combination of colors for a given point as all primary colors whose corresponding digit is 1. Each of the points has a unique representation, so each combination of primary colors will be unique.

My specific question is: can you prove that $\lceil \log_2 n \rceil$ is sufficient? That no lower value of $k$ will work is easy: then the power set of the $z_l$'s will have magnitude less than $n$, so by the Pigeonhole Principle, there will be two strings that will not be distinguished any of the $z_l$'s. So $k \ge \log_2 n$. An easy upper bound is $\binom{n}{2}$. Since the strings are pairwise $L$-distinguishable, we can pick a string for subset of the $x_i$'s of size two.

But is $\lceil \log_2 n \rceil$ really all you need? I am looking for either a formal proof that this is the case, or an example of a language $L$ and $n$ pairwise $L$-distinguishable strings for which there do not exist $\lceil \log_2 n \rceil$ strings distinguishing the $x_i$.


1 Answer 1


Your solution is phrased in terms of the analogy given, not the original question. Each color in the analogy corresponds to a string $z_l$ in the original. Likewise, each point in the analogy corresponds to string $x_i$.

I think your logic is sound, you just need to do a sort of find/replace on your solution.

  • $\begingroup$ I know. What I am wondering about is how to prove that the two problems as phrased are indeed equivalent. If I can better understand that, then translating my solution will be no problem. $\endgroup$
    – A.E
    Oct 30, 2013 at 17:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .