# Is it possible to prove that $L$ is a regular language?

Let $L = \{a^{f(m)} | m \geq 1 \}$ where $f: \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ is monotonically increasing and complies that for all $n \in \mathbb{Z}^+$ there is $m \in \mathbb{Z}^+$ such that $f(m+1) - f(m) \geq n$.

Regards,

Alex.

-

## migrated from cstheory.stackexchange.comAug 16 '11 at 4:57

This question came from our site for theoretical computer scientists and researchers in related fields.

please consult the faq: cstheory is for research level questions. We have a strict policy of no homework questions. – Artem Kaznatcheev Aug 16 '11 at 3:13
Please read the FAQ. I am migrating the question to Math.SE. – Kaveh Aug 16 '11 at 4:56

We will use the pumping lemma to prove that $L$ is not regular.

Suppose $L$ were regular and let $p$ be its pumping lenght. Let $m$ be such, that $f(m) \geq p$ (such $m$ exists!). Let $w=a^{f(m)}$. As $w\in L$ there exist words $x,y$ and $z$ such that $|y| \geq 1$, $|xy| \leq p$ and $\forall n\in \mathbb{N}, xy^n z\in L$.

It follows, that $\forall n\in\mathbb{N_0}\exists m, |xz|+n|y| = f(m)$. But this cannot be as there exist arbitrarily large $m$, such that $f(m+1) - f(m) > |y|$.

-

I think $L$ is not regular. Here's an idea: let $k$ be the number of states of a minimum DFA that accepts $L$. Since the alphabet has one symbol only, this DFA must be a cycle (why?). For an appropriate $n$ there exists $m$ such that $f(m+1)-f(m)>k$, which is a contradiction, because there would be some $c$ between $f(m)$ and $f(m+1)$ such that $a^c$ belongs to $L$ (why?). However, $c$ can not be the image of an integer by $f$ (why?).

I leave the details to you, first because given your only other question in this website I suspect that I'm doing your homework, and second because I gave you enough hints already :) Good luck!

Update: I'm a new user, and this was my first answer. I realize now that the website is for research-level questions only. That said, this question looked like homework to me, so maybe somebody will want to close the topic.

-
I see you have a publication. You know $LaTeX$. Why not use it? :) – Pratik Deoghare Aug 16 '11 at 0:22
I didn't know we could use LaTeX. This is wonderful! Thanks! – Janoma Aug 16 '11 at 1:54