Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular

Question

I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me?

This was an exam question from previous year. I looked your answers, but I can't really understand Yuval's solution and Matt's solution would be too long for an exam question.
From lecture we were given 3 methods to prove non-regularity. I thought that 3 methods are all classical methods to prove non-regularity, but it seems like the third one isn't so 'classical'. The third one is as follows:

Let $\ L \subseteq (\Sigma_{bool})^* $ be a regular language. Let $\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \} $ for every$\ x \in (\Sigma_{bool})^*$. Then there exists a constant $\ c$, such that for all $\ x,y \in (\Sigma_{bool})^* $

$\ K(y) \leq \lceil log_2(n+1)\rceil+c $

if $\ y $ is the n-th word in the language $\ L_x $.

I'd like to show my proof using this method.

Suppose that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is regular.
We have ${2(n+1)}\choose{n+1}$ = ${2n \choose n+1}{2 \choose {0}} $ + ${2n \choose n}{2 \choose {1}}$ + ${2n \choose n-1}{2 \choose {2}}$.
i.e. ${2(n+1)}\choose{n+1}$ = $2*{2n \choose n}$ + ${2n \choose n+1}$ + ${2n \choose n-1}$ . $(\ast)$
Then we define $\ L_n = L_{0^{{{2n}\choose{n}}+{{2n}\choose{n+1}}}}:=\{ y \in (\Sigma_{bool})^* | 0^{{{2n}\choose{n}}+{{2n}\choose{n+1}}}y\in L \} $ for every $n\in \mathbb{N} $. Let $y_1$ be the first word in $L_n$. Obviously $y_1= $ $0^{{{2n}\choose{n}}+{{2n}\choose{n-1}}} $ by $(\ast)$. By the theorem, there exists a constant $c$ ,such that for any $n \in \mathbb {N}$,
$\ K(y_1) \leq \lceil log_2(1+1)\rceil+c $.
Thus we can bound the Kolmogorov complexity of all elements in $S=\left\{0^{{{2n}\choose{n}}+{{2n}\choose{n-1}}} | n\in \mathbb {N}\right\}$ by constant $c$. However, this is an infinite set , we have only limited number of programs of length $\le c$. So we can't bound the Kolmogorov complexity of the elements in $S$, this means $L$ can't be regular.

If you don't know this theorem, you can find it here Proof of non-regularity, based on the Kolmogorov complexity. I don't know if my solution is right or not, if you find any problems please let me know.

Answer 1

A unary language (i.e., a subset of $0^*$) $L$ is regular iff the set $S = \{ n : 0^n \in L \}$ is eventually periodic. In particular, if $L$ is regular then either $S$ is finite or $S$ has positive density (in the following strong sense: $|S \cap [n]|/n$ converges to a positive number). However, in your case the set $S$ is infinite yet has density zero.

In the same way, we get that the following languages are not regular: $$ \{0^{\lfloor n\log n \rfloor} : n \in \mathbb N\}, \{0^{n^2} : n \in \mathbb N\}, \{0^{2^n} : n \in \mathbb N\}, \{0^{n!} : n \in \mathbb N\} $$ and so on.

Answer 2

Suppose for contradiction that $L = \{0^{2n \choose n} : n \in \mathbb{N}\}$ is a regular language. Then by the definition of a regular language there exists a deterministic finite automaton (DFA) that recognizes $L$. Let $D$ be such a DFA and let $|D|$ denote the number of states in $D$.

1. Choose an $n$ such that ${2n \choose n} > |D|$ and define $S = 0^{2n \choose n}$. Clearly $S \in L$ by its construction.

2. Since $S$ has length ${2n \choose n} > |D|$ by the pigeonhole principle there must be at least one state in $D$ that is visited at least twice, call this state $d$.

3. Divide $S$ into three pieces as follows $S = xyz$ where $x$ is the portion of $S$ that comes before the first occurrence of $d$, $y$ is the portion of $S$ that occurs between the first and second occurrence of $d$, and $z$ be the remainder of $S$. (Note, $x$ and $z$ may be empty but $y$ must be at least length 1).

4. Now by the pumping lemma, we can repeat $y$ as many times as needed and therefore every string $S' = xy^kz, k \in \mathbb{N}$ will be accepted by $D$.

5. We just need to find a suitable $k$ so that $S'$ isn't also in $L$. (There may be many ways of doing so but here's one way). Observe that ${2n \choose n} = \frac{(2n)!}{(n!)^2}$ and

$$\lim_{n\rightarrow\infty} \frac{(2(n+1))!/((n+1)!)^2}{(2n)!/(n!)^2} = \lim_{n\rightarrow\infty} \frac{(2n+2)(2n+1)}{(n+1)^2} = \lim_{n\rightarrow\infty} \frac{4n^2 + 6n + 2}{n^2 + 2n+ 1} = 4$$

What this tells us is that incrementing $n$ by one roughly quadruples the length of the string, and therefore the gaps between lengths of the strings will eventually be larger than $2|y|$. Therefore there exists an $n'$ such that $${2(n' +1) \choose n' +1 } - {2n' \choose n'} > 2|y|$$

and therefore if we let $k$ be such that $|xy^kz|$ is the smallest possible value that satisfies $$|xy^kz| > {2n' \choose n'}$$ then $D$ will accept $xy^kz$ but $xy^kz \notin L$ since $|xy^kz|$ can't be written as ${2n \choose n}$.

6. This creates a contradiction with $D$ being a DFA that recognizes $L$ and therefore $L$ is not a regular expression.

Okay, that was a bit long but I'll break it down step by step.

In 1. We basically just come up with a string $S$ in $L$ that is longer than $D$ has states.

In 2. we use that the string is longer than $S$ and so it must see at least one state twice (because otherwise, we'd see each state at most once and then $S$ wouldn't be longer than $D$ has states.) We call that state $d$.

In 3. We take advantage of the fact we visit a state twice and chop $S$ into three pieces, the part before we see $d$ (we call this $x$), the part between seeing $d$ the first time and seeing $d$ the second time (we call this $y$), and then the rest of $S$ (we call this $z$).

In 4. We use the pumping lemma that tells us that we can just repeat $y$ over and over because we started $y$ at $d$ and ended at $d$ so taking the same string $y$ a second time will go along the exact same loop back to $d$ and we can do that over and over and therefore we know that $xy^kz$ will be accepted.

The first four steps are common to every pumping lemma proof and are pretty much automatic in every proof that you'll do.

In step 5. We need to find a $k$ so that we don't end up back in $L$. Often this is the step that takes some creativity. What I have done is shown that the lengths of the strings in $L$ become more and more spaced out as $n$ grows, and eventually, the gap is big enough that $2|y|$ fits inside, and therefore there is a number of repeats of $y$ that creates a string that won't end up being ${2n \choose n}$ long for any $n$. The reason that we need to do this is that we don't want to add onto our string $S$ and accidentally end up back in $L$ since that wouldn't be a contradiction. (Basically if we weren't careful here we could go from ${2n \choose n}$ to ${2(n+1) \choose n+1}$ for example and that wouldn't put our string outside of $L$).

In 6. we just state that in 5. we found a string that isn't in $L$ but is accepted and therefore we have a contradiction (again this is in every pumping lemma proof).

Answer 3

The numbers (2n over n) are a quickly growing sequence.

Assume you have a state machine for L. After processing say (20 over 10) 1's you are in a state that is accepting (obviously because (20 over 10) 1's are in the language L), and further 1's go to non-accepting states until there are a total of (22 over 11) 1's. So you have an accepting state $S_{10}$, where you reach another accepting state for the first time after exactly (22 over 11) - (20 over 10) 1's.

After (22 over 11) 1's you end up in a state $S_{11}$ that is also accepting, where you reach another accepting state for the first time after (24 - 12) over (22 - 11) 1's. Since (2n over n) grows faster and faster, the number of 1's needed to reach another state is larger, so the two states that are involved are different.

With the same argument, you can show that after processing (2n over n) 1's, and after processing (2n' over n') 1's for different n and n', you must end up in two states $S_n$ and $S_{n'}$ which must be different. Since there is an infinite number of possible n's, there must be an infinite number of different states. So you don't have a finite state machine, so the language is not regular.

This is true for any language $L = \{ 1^{f(n)} \}$ where f(n+1) - f(n) is strictly increasing (which you have to show for f(n) = (2n over n)). Actually, it is true if f(n) is non-decreasing but the sizes of the gaps f(n+1) - f(n) become arbitrarily large, for example if f(n) = n-th prime number.

This is a special case. The pumping-lemma that you read about takes the same idea (proving that a state machine cannot have a finite number of states) but is much more strict, so it works for many more possible languages.