[Solved]: Proving that any CF language over a 1 letter alphabet is regular

Problem Detail: 

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far:

Let L be a context free language. So, $L$ satisfies the pumping lemma. Let $p$ be $L$'s pumping constant. Let $L = L_1 \cup L_2$ where $L_1$ consists of $w$ where $|w| < p$ and and $L_2$ consists of $w$ where $|w| >= p$. We have a single letter alphabet and since $L_1$ has a restriction on the length of its words, $L_1$ is a finite language. Finite languages are regular so $L_1$ is regular. If I can show that $L_2$ is regular, I can use the fact that the union of regular languages is regular. But I am struggling on showing that $L_2$ is regular. I know that since $w \in L_2$ has to satisfy $|w| >= p$, by the pumping lemma, $w$ can be written as $w = uvxyz$ where $|vxy| <= p$, $|vy| > 0$ and $\forall t >= 0$, $uv^txy^tz \in L$. Since we have a single letter alphabet (say the letter is $a$), $uv^txy^tz = uxz(vy)^t = uxz(a^{|vy|})^t \in L$. Now what?

Asked By : ilikecats

Answered By : Karolis Juodelė

You have shown that for any given $w = uvxyz = a^{|uxz|+|vy|}$ there is a regular language $L_w = a^{|uxz|+|vy|\cdot t} \subset L_2$. Now you need to show that $\bigcup L_w = L_2$ and that this can be a finite union. Note that $|vy| \leq p$ and that $a^{(|uxz|+|vy|)+|vy|\cdot t} \subset a^{|uxz|+|vy|\cdot t}$ so not all values of $|uxz|$ matter.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40791