3
$\begingroup$

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?

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

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)

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