# Lengths of “all-accepted” words in Context Free languages

If $$L$$ is a Context Free language, it can happen that for some $$n$$, all words of length $$n$$ are in $$L$$. If we consider the set $$A_L$$ of such lengths represented in unary, we may guess that such set is Context Free (and hence regular), but it is not the case.

More formally; if $$L \in CF$$ define:

$$A_L = \{ 1^n \mid |w|=n \Rightarrow w \in L \}$$

There are CF languages for which $$A_L \notin REG$$.

The example I have in mind uses the sequence of tape configurations (alternating straight/reverse order like in the proof of the undecidability of $$L = \Sigma^*$$) of a valid Turing machine computation that on input $$x$$ (in binary), writes $$1^x$$ on the tape and halts.

Before spending more time in formalizing it, I wonder if there is a simpler example, or if I can find it in some books/papers (I made some searches but probably I'm using the wrong terms).

The shortest word in $$A_L$$ is not bounded by a recursive function in the size of a given context-free grammar describing $$L$$. See here for more results in that direction: https://doi.org/10.4230/LIPIcs.STACS.2020.16
• Thank you! I had to download it from arXiv because the one from your link misses some parts. By the way, the set $A_L$ built from the CF language $L$ they used to prove the undecidability of "Exists $\ell$ s.t. $\Sigma^\ell \subseteq L$?" (and the unboundedness w.r.t. the size of the grammar) is regular :-) – Marzio De Biasi Jul 14 '20 at 13:10