I would like to prove that any context free language over a 1 letter alphabet is

Question

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=L1?L2 where L1 consists of w where |w|<p and and L2 consists of w where |w|>=p. We have a single letter alphabet and since L1 has a restriction on the length of its words, L1 is a finite language. Finite languages are regular so L1 is regular. If I can show that L2 is regular, I can use the fact that the union of regular languages is regular. But I am struggling on showing that L2 is regular. I know that since w?L2 has to satisfy |w|>=p, by the pumping lemma, w can be written as w=uvxyz where |vxy|<=p, |vy|>0 and ?t>=0, uvtxytz?L. Since we have a single letter alphabet (say the letter is a), uvtxytz=uxz(vy)t=uxz(a|vy|)t?L. Now what?

Explanation / Answer

You have shown that for any given w=uvxyz=a|uxz|+|vy| there is a regular language Lw=a|uxz|+|vy|?t?L2. Now you need to show that ?Lw=L2 and that this can be a finite union. Note that |vy|?p and that a(|uxz|+|vy|)+|vy|?t?a|uxz|+|vy|?t so not all values of |uxz| matter.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects