132 views
Is it necessary for the CFL string lenghts to be in AP if the alphabet is a singleton set?

No, it is not necessary for the CFL string lengths to be in AP if the alphabet is a singleton set.

All regular languages are also Context Free Languages. Now consider a regular language

$L = (11111+1111111)^{*}$  = {11111, 1111111, 1111111111….}

Notice the length of the strings in the language : {5,7,10,12,14,15,17..}, which is clearly not in AP.
by
525 points

but it can generate all the strings after a certain lenght if I am not wrong. Can you give an example of a language that is not regular but context free and still not in AP over a single alphabet ?
It's sufficient but not necessary condition

@xiuhan, I think we cannot have a context free language which is not a regular language over a singleton alphabet. Instead every context-free language over a singleton alphabet, generates a regular language. See this proof http://www.iasi.cnr.it/~adp/Teach/ALT10/ContextFreeOnSingletonSigma.pdf

But we can have a language over single alphabet which is not a context free language. For example

L = {$a^{2^{n}}$ | n $\geq$ 0} is not a context free language

If over a singleton alphabet we cannot have a CFL that is not regular doesn’t this mean that the language must be in some form of AP since it is regular?
@xiuhan, Is there anywhere you read, RL strings lengths should be in AP?
i think in applied gate course shrikanth sir has made a video on special case of pumping lemma that suggests that

so it must be true
@Shaik Masthan sir, my coaching teacher also said that the special case and pumping lemma implies that string lengths must be in AP. This is not only true for CFL but also Regular languages.

No, its not necessary. “If the string lengths of a language over an alphabet (which is a singleton set) is in AP, then definitely the language is Regular (and hence CFL). But it is not necessary for the string lengths to be in AP for the language to be Regular.”  From here onwards I will assume that the alphabet to be $\Sigma = \{ a \}$. All the languages which I will be mentioning will be defined over this alphabet ${\Sigma}$.

One obvious reason is that, you can consider any finite language where the string lengths are not in AP. That language will be definitely regular and hence CFL. For example: $L = \{ a, a^3, a^4 \}$. Clearly the string lengths are not in AP but still the language is CFL.

But I think, what you are trying to ask is whether it is necessary for string lengths to be in AP for an infinite language to be CFL. Even in this case the answer is no.

Consider two languages $L_1 = \{ a^{5n} \, \vert \, n \geq 0 \}$ and $L_2 = \{ a^{6n} \, \vert \, n \geq 0 \}$. Both the languages $L_1$ and $L_2$ are regular since the string lengths are in AP. Now consider a new language $L_3$ which is $L_1 \cup L_2$. Since, regular languages are closed under union operation $L_3$ is regular. Therefore, $L_3 = \{ a^0, a^5, a^6, a^{10}, a^{12} ...\}$. Clearly the string lengths of $L_3$ are not in AP but $L_3$ is regular and hence it is CFL.

by
71 points