4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

This is a special case of Parikh's theorem. You can find a proof in lecture notes of Lindqvist (linked in the Wikipedia article). In fact, Parikh's theorem is a bit more general: it states that the histograms of all words in a context free language are "regular" (for an exact statement, see the link).

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