7
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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 :-) $\endgroup$
    – Marzio De Biasi
    Jul 14, 2020 at 13:10

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.