<p>The shortest word in <span class="math-container">$A_L$</span> is not bounded by a recursive function in the size of a given context-free grammar describing <span class="math-container">$L$</span>. See here for more results in that direction:
<a href="https://doi.org/10.4230/LIPIcs.STACS.2020.16" rel="noreferrer">https://doi.org/10.4230/LIPIcs.STACS.2020.16</a></p>

CC BY-SA 4.0
2020-07-14T13:10:11.793Z
Thank you! I had to download it from [arXiv](https://arxiv.org/abs/1702.03961) 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
CC BY-SA 4.0
2020-07-13T18:51:45.690Z
2020-07-13T18:51:45.690Z
Hermann Gruber
<p>If <span class="math-container">$L$</span> is a Context Free language, it can happen that for some <span class="math-container">$n$</span>, all words of length <span class="math-container">$n$</span> are in <span class="math-container">$L$</span>. If we consider the
set <span class="math-container">$A_L$</span> of such lengths represented in unary, we may guess that such set is Context Free (and hence regular), but it is not the case.</p>
<p>More formally; if <span class="math-container">$L \in CF$</span> define:</p>
<p><span class="math-container">$A_L = \{ 1^n \mid |w|=n \Rightarrow w \in L \}$</span></p>
<p>There are CF languages for which <span class="math-container">$A_L \notin REG$</span>.</p>
<p>The example I have in mind uses the sequence of tape configurations (alternating straight/reverse order like in the proof of the undecidability of <span class="math-container">$L = \Sigma^*$</span>) of a valid Turing machine computation that on input <span class="math-container">$x$</span> (in binary), writes <span class="math-container">$1^x$</span> on the tape and halts.</p>
<p>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).</p>

<context-free>
Lengths of "all-accepted" words in Context Free languages
Marzio De Biasi
# Lengths of "all-accepted" words in Context Free languages

(Asked by: username_0 on 2020-07-13)

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).

**Tags:** context-free

---

## 1 answers

### Answer by username_1 on 2020-07-13. Score: 7

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>

> **Comments:**
> **username_0**: Thank you! I had to download it from [arXiv](https://arxiv.org/abs/1702.03961) 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 :-)  

---

