0
$\begingroup$

genQ

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!

$\endgroup$
0
$\begingroup$

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.

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