# Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

I want to show that for any language $L \subseteq \{ a \}^*$, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages.

I know that every regular language is also a context free language so I tried to show that direction of the proof first but ran into some difficulties.

Is there a more logical approach to this? Would I have to show that the conditions for both the pumping lemma for regular languages and the pumping lemma for context free grammars are equivalent for this language?

• Do you know a special property that unary context-free languages have?
– Raphael
Mar 26 '14 at 8:47
• @Raphael I'm not aware of this special property of unary languages but thanks of for leading me in the right direction. Mar 26 '14 at 11:40
• Does this characterisation of CFL help?
– Raphael
Mar 26 '14 at 14:54

let $z \in L$ such that $|z| \geq n$ (where $n$ is the lemma's constant). By the pumping lemma for CFL, we know that we can write $z=uvwxy$ such that:

1. $|vwx| \leq n$
2. $|vx| \geq 1$
3. for all $i \geq 0$: $uv^iwx^iy \in L$

Because $L$ is over an unary alphabet, we can change the order of the sub-words and the word ($z$) will not change, meaning we can also write $z=wvxuy$.

So. for all $i \geq 0$, $uv^iwx^iy = wv^ix^iuy = w(vx)^iuy$. Let's write a little different: $u' = w, v' = vx, w' = uy$. and we have that $u'(v')^iw' \in L$.

It's easy to see that $|u'v'| \leq n$ and $|v'| \geq 1$, So we can conclude that for the same $n$, the conditions of pumping lemma for regular languages holds.

It might be worth mentioning that every CFL of unary alphabet is also regular (We know that even though a language satisfies the pumping lemma for regular/CF languages, it does't mean that the language is regular/CF).

It can be shown using Parikh's theorem, and showing that for every semi-linear set $S \subseteq \mathbb{N}$ there is a regular language $L$ such that $\Psi (L)=S$ (or $p(L)$ using wikipedia's notations)