## 2 Answers

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.

### 7 Comments

@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

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.