# How to prove this language is not regular (via Fooling Set)

By using this fooling set, I am able to prove that the concatenation of bz is in the language L, but I still need to prove that az is not in the language to complete the proof.

This is also the point that the ceiling function is very tricky to deal with. It is also where I am lost.

Any hints and suggestions will be appreciated!

Let $s_1 < s_2 < \cdots$ be a subset of $\mathbb{N}$ with the following property:
$$\limsup_{n\to\infty} s_{n+1}-s_n = \infty.$$
I will show that the language $L = \{ 0^{s_n} : n \geq 0 \}$ isn't regular using the fooling set method.
The first step is to find indices $i_1 < i_2 < \cdots$ such that $$s_{i_1+1}-s_{i_1} < s_{i_2+1}-s_{i_2} < \cdots.$$ This can easily be done using the given property.
Our fooling set is $\{ 0^{s_{i_n}} : n \geq 0 \}$. To show that this is a fooling set, let $j < k$, and consider the words $x = 0^{s_{i_j}}$ and $y = 0^{s_{i_k}}$. Let $z = 0^{s_{i_j+1}-s_{i_j}}$. Then $xz = 0^{s_{i_j+1}} \in L$ but $yz = 0^{s_{i_k}+s_{i_j+1}-s_{i_j}} \notin L$ since by construction, $$s_{i_k} < s_{i_k}+s_{i_j+1}-s_{i_j} < s_{i_k+1}.$$
More generally, a unary language $\{0^s : s \in S\}$ is regular if and only if there exist $N,M$ such that $n \in S$ iff $n+M \in S$ for all $n \geq N$. There are many ways to show it, the most elementary being that a graph of unary DFA consists of a path leading to a cycle. This result implies yours.